Number Theory

Time Limit: 1 Second

Memory Limit: 65536 KB

Description

Given an integer $N$, calculate the smallest positive integer that is not a sum of distinct divisors of $N$.

Input

There are multiple test cases. The first line of the input contains an integer $T$ (about 2000), indicating the number of test cases. For each test case:

The first line contains one integer $N$ ($1 \le N \le 10^{18}$).

Output

For each test case output one line indicating the answer.

Sample Input

5
102
28
8
5
1

Sample Output

13
57
16
2
2

Hint

None

Source

None

提交代码