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

Discussion

Statistics


39% Solution Ratio

EgorKulikovEarliest, 3w ago

fsshakkhorFastest, 0.2s

EgorKulikovLightest, 131 kB

magic_kiriShortest, 2589B

Submit

Login to submit

Editorial

To solve this problem we need to know about prime gaps. In 1018 range, the maximum difference two co... Read more...

Related Contests

Criterion 2020 Round 4 Ended at 2020-03-13 11:30:00 +0000 UTC