Story of Totient Function

Euler's totient function counts the number of positive integers up to a given integer N that are relatively prime to N. Formally, it is the count of integers K in range 1 ≤ K ≤ N for which the greatest common divisor gcd(N, K) equal to 1. It is denoted as ϕ(N).

Ahsan has an integer A. He wants to find an integer B such that B is greater than A and ϕ(B) > ϕ(A). There can be many such integers that satisfy the conditions. So he wants to find the smallest such B.

Input

First line contains an integer T(1 ≤ T ≤ 10), denoting the number of test cases.
Each of the next T lines contain a single integer A(1 ≤ A ≤ 1018).
It is guaranteed that the product of all given A will not exceed 1018.

Output

For each test case, print the smallest B that satisfies the conditions.

Sample

Input	Output
10 1 2 3 4 5 6 7 8 9 10	3 3 5 5 7 7 11 9 11 11