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 \)