Let $P(X)$ be the parity of a number which is defined as N, where N is the number of integers that divide X.
You are given a number X and you have to determine the smallest number Y such that Y > X and $P(Y) != P(X)$.

Input format

• First line: T (number of test cases)
• For each test case: X

Output format
For each test case, print the required answer on a separate line.

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