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.

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¹⁸.

For each test case, output in a separate line the minimal possible number of hares in the gang k.