Steve is playing a game with numbers. He picks up a random positive number N and finds the largest positive number not bigger than N that has the most divisors. As N becomes larger it’s more and more difficult for Steve to avoid mistakes when counting the divisors and he asks you to write a program. You argue that it is a very easy task to just find the divisors and suggest that you could solve the original task of Steve as well. Input You are given a number of tests T (T ≤ 50000). Each test on a single line specifies a number N (1≤N ≤106). Output You need to find the largest number not bigger than N that has the most divisors. For each test output one line containing the answer to the game. Sample Input 3 1 10 37 Sample Output 1 10 36