Today is a very good day in CSEmpur because Tuktuki has bought N gifts! Tuktuki wants to give these gifts to all of her K friends. So she did the obvious and called them all. She was planning to equally divide the gifts among her friends (i.e. equal K shares) so that each gets X gifts. There would be some remainder gifts (< K) which she would take for herself. But after everyone arrived, she counted to find one of her friends missing. You might be thinking that now Tuktuki has to do the math all over again and compute the new X. But surprisingly, after doing the calculations, she finds that everyone will still get X gifts. Now this has intrigued me, and so I am giving you this task: Given a N, you have to output the minimum K such that, after one friend being missing, Tuktuki still gives away same number of gifts to each of her friend.
Input
First line contains T number of testcases. Next T lines each contain a number N.
1 ≤ T ≤ 105
1 ≤ N ≤ 1018
Output
For each N, output the minimum K in a single line.
Sample
| Input | Output |
|---|---|
6 1 5 10 50 100 1000000000000 | 3 4 5 10 14 1001001 |
For n = 10, note that if we divide 10 gifts among 5 friends, each get 2. If we divide them among 4 friends, again each get 2. | |
