Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4040
Number Theory

Time Limit: 1 Second      Memory Limit: 65536 KB

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

Author: LIU, Mingrui
Source: ZOJ Monthly, June 2018
Submit    Status