A gang of k hares robbed a vegetable storehouse and stole n heads of cabbage.
At that time, a fox was running by and offered to divide the cabbage among the
gangsters. The hares agreed, but their condition was that they would get equal
numbers of heads and the fox could take the remainder of less than k
heads as a payment for his service.
Meanwhile, as the fox was dividing the cabbage, one more hare joined the gang,
who didn't take part in the robbery. He got the same share as other gangsters
but remained unnoticed. How could that happen? The reason was that each hare
got the same number of heads as if the newcomer hare had not been present.
Find the minimal number of hares in the gang for which that could happen.
Input
You are given several test cases. The first line contains the number of cases t,
1 ≤ t ≤ 30000. In each of the next t lines you are given
the integer n for the corresponding case,
1 ≤ n ≤ 10^{18}.
Output
For each test case, output in a separate line the minimal possible number of hares
in the gang k.
Sample
input  output 

3
9
11
18
 5
4
5

Problem Author: Alexander Ipatov
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009