시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB0000.000%

문제

Rikka is taking the undergraduate cryptography course this year. In the class, it is mentioned that a new method of factorization was recently discovered, which is considered a historic breakthrough in cryptography. Rikka believes that there will be comparable algorithms for some specific class of numbers with simpler goals.

Now you are asked to design and implement such a "factorization" algorithm: given an integer $m$, print an integer $n$ such that $$m = \frac{n \varphi(n)}{2} = \sum\limits_{\begin{array}{c}1 \le i \le n, \\ \mathrm{gcd}(i, n) = 1\end{array}} i \text{.}$$ It is guaranteed that such an $n$ exists in all the test cases.

입력

The first line of input contains an integer $T$ ($1 \le T \le 51$), the number of test cases.

The $i$-th of the following $T$ lines contains a single integer $m_i$ ($0 < m_i < 10^{36}$).

출력

For each test case, print an integer $n_i$ for the corresponding $m_i$. It is guaranteed that the answer exists in every test case. If there are several possible answers, print any one of them.

예제 입력 1

3
20
21
475750381222420656586462245096576000

예제 출력 1

10
7
1497700821900508526