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.