Migrated from Lutece 2499 An Easy Math Problem III

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一个环上有 $n$ 个点，相邻的两个点之间的距离为 $1$ 米，第 $n$ 个点与第 $1$ 个点相邻。

小 A 初始时在第 $1$ 个点，第 $i$ 个时刻向前走 $i$ 米，求最小正整数 $x$，使得第 $x$ 时刻结束正好回到第 $1$ 个点。

Input

第一行一个整数 $T$ $(1\leq T\leq 100)$，表示数据组数；

接下来一个整数 $n$ $(1\leq n\leq 10^{12})$。

Output

一共 $T$ 行，每行一个正整数表示答案。

Samples

5
2
4
6
8
10

3
7
3
15
4

Resources

2020 UESTC ICPC Training for Math and Geometry