Consider the following information:

• If the number of integers that divide a number N is even, then P(N) =0. 
• If the number of integers that divide a number N is odd, then P(N) = 1.

Task

Now, you are given a number $X$.

Your task is to determine the smallest number $Y$ such that $Y > X$ and $P(Y) \neq P(X)$.

Input format

• The first line contains $T$ denoting the number of test cases.
• The first line of each test case contains $X$.

Output format

For each test case, print the smallest number $Y$ such that $Y > X$ and $P(Y) \neq P(X)$ in a new line. 

Constraints
$1 \le T \le 10^{5}$
$1 \le X \le 10^8$