Rikka 今年正在修读本科密码学课程。课上提到，最近发现了一种新的因式分解方法，这被认为是密码学领域的一次历史性突破。Rikka 相信，对于某些具有更简单目标的特定类别的数字，也会存在类似的算法。

现在请你设计并实现这样一种“因式分解”算法：给定一个整数 $m$，输出一个整数 $n$，使得 $$m = \frac{n\phi(n)}{2} = \sum_{\substack{1 \le i \le n, \\ \gcd(i, n) = 1}} i$$ 题目保证在所有测试用例中，这样的 $n$ 都存在。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 51$)，表示测试用例的数量。 接下来的 $T$ 行中，第 $i$ 行包含一个整数 $m_i$ ($0 < m_i < 10^{36}$)。

输出格式

对于每个测试用例，输出对应的整数 $n_i$。题目保证每个测试用例都有解。如果存在多个可能的答案，输出其中任意一个即可。

样例

输入 1

3
20
21
475750381222420656586462245096576000

输出 1

10
7
1497700821900508526