Codeforces Round 952 (Div. 4) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

math

number theory

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Maximum Multiple Sum

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven an integer $$$n$$$, find an integer $$$x$$$ such that:

- $$$2 \leq x \leq n$$$.
- The sum of multiples of $$$x$$$ that are less than or equal to $$$n$$$ is maximized. Formally, $$$x + 2x + 3x + \dots + kx$$$ where $$$kx \leq n$$$ is maximized over all possible values of $$$x$$$.

Input

The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

Each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$).

Output

For each test case, output an integer, the optimal value of $$$x$$$. It can be shown there is only one unique answer.

Example

Input

2315

Output

3 2

Note

For $$$n = 3$$$, the possible values of $$$x$$$ are $$$2$$$ and $$$3$$$. The sum of all multiples of $$$2$$$ less than or equal to $$$n$$$ is just $$$2$$$, and the sum of all multiples of $$$3$$$ less than or equal to $$$n$$$ is $$$3$$$. Therefore, $$$3$$$ is the optimal value of $$$x$$$.

For $$$n = 15$$$, the optimal value of $$$x$$$ is $$$2$$$. The sum of all multiples of $$$2$$$ less than or equal to $$$n$$$ is $$$2 + 4 + 6 + 8 + 10 + 12 + 14 = 56$$$, which can be proven to be the maximal over all other possible values of $$$x$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/24/2024 03:34:06 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|