ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1705. Gangster Hares

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ 1018.

Output

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

Sample

inputoutput
3
9
11
18
5
4
5
Problem Author: Alexander Ipatov
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009