Given an integer N <= 10²⁵⁰⁰⁰ find the smallest m <= N such that m/phi(m) is maximum. Where phi is euler's totient function.

Input

The first line in the input gives the number of test cases T (T <= 200), and then T lines follow each containing an integer N.

Output

Output the smallest required value of m.

Example

Input:
1
10

Output:
6