Problem

A positive integer n is an antiprime number, when it has more divisors than any positive integer, that is less than n. These are examples of antiprime numbers: 1, 2, 4, 6, 12 and 24. Write a program to find the greatest antiprime number which is not greater than n.

Input

The first line will give the number of test cases T, then there are T lines, each contains an integer n, 1 <= n <= 2000 000 000.

Output

For each test case, your program should write exactly one integer - the greatest antiprime number not greater than n.

Sample Input

2
3
1000

Sample Output

2
840