# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Story of Totient Function

By fsshakkhor · Limits 1s, 512 MB

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

InputOutput
10
1
2
3
4
5
6
7
8
9
10

3
3
5
5
7
7
11
9
11
11


### Statistics

40% Solution Ratio

EgorKulikovEarliest, Mar '20

serotoninFastest, 0.1s

EgorKulikovLightest, 131 kB

serotoninShortest, 1908B