역사적인 돌파구

Rikka는 올해 학부 암호학 강의를 듣는다. 수업에서 최근 새로운 소인수분해 방법이 발견되었고, 이것이 암호학의 역사적인 돌파구로 여겨진다는 내용이 언급되었다. Rikka는 더 단순한 목표를 가진 특정 부류의 수에 대해서도 이에 필적할 만한 알고리즘이 존재하리라고 생각한다.

이제 이런 "소인수분해" 알고리즘을 설계하고 구현해야 한다. 정수 $m$이 주어졌을 때, 다음을 만족하는 정수 $n$을 출력하라.

$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{.}$

이러한 $n$이 모든 테스트 케이스에서 존재함은 보장된다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 51$)

이어지는 $T$개의 줄 중 $i$번째 줄에는 정수 $m_i$가 하나씩 주어진다. ($0 < m_i < 10^{36}$)

각 테스트 케이스마다 해당하는 $m_i$에 대한 정수 $n_i$를 출력한다. 모든 테스트 케이스에서 답이 존재함은 보장된다. 가능한 답이 여러 개라면 그중 아무거나 출력해도 된다.