Katari and his love for Mex
Tag(s):

## Prime Factorization, Very-Easy, Very-Easy

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
4
6
SAMPLE OUTPUT
2
2
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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...