Katari and his love for Mex
Problem
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.
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
Mex(4) can be calculated as:
Divisors of 4 = {1, 2}
Mex of 1 = 0.
Mex of 2 = Mex(Mex of divisors of 2) = Mex{Mex(1)} = Mex{0} = 1.
Mex of 4 = Mex{Mex(1),Mex(2)} = Mex{0,1} = 2.
