As we all know, Katari is very desperate about winning every game he plays. So, he needs your help to win the games using your knowledge on Mex . Mex is an ancronym for Minimum Excludant.

Mex of a number in this game can be defined as the minimum positive integer that is not in the set containing the Mex of all the divisors of the number.

Input :

First line of the input contains t, number of test case.
Next t lines contains a number n, to which you have to find the Mex.
1 <= t <= 100000
1 <= n <= 10^11

Output :

Output t lines each line containing the value of Mex of number.