#11960Divisor Game

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.

3
1
10
37

1
10
36