23145번 - Historic Breakthrough 스페셜 저지다국어

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.