spoj#NDIVPHI2. N DIV PHI_N (Hard)
N DIV PHI_N (Hard)
Given an integer N <= 1025000 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