Need help with this number theory problem. Give me some hints, please.
Given an integer N <= 10^40 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.
Sample Input:
1 10
Output: 6
