Factors

Find a number between 1 and n (inclusive) that has the highest number of prime factors in its prime factorization. If there are multiple numbers with the same maximum number of prime factors, select the largest one.

For instance, consider the numbers from 1 to 7. The numbers 2, 3, 5, and 7 are prime, each having one prime factor. The number 1 has zero prime factors. The factorizations of 4 = 2 * 2 and 6 = 2 * 3 each have two prime factors. Thus, for n = 7, the answer is 6.

Input

The first line contains the number of test cases. Each test case consists of a single integer n (1 ≤ n < 2^31 - 1).

Output

For each test case, output a single line with the largest number from 1 to n that has the maximum number of prime factors among all numbers from 1 to n.

Examples