Factors#2700
Find the number between and (inclusive) that has the maximum number of prime factors in its prime factorization. If there are several such numbers, select the largest one among them.
For example, consider the numbers from to . The numbers , , , and are prime and each has one prime factor. The number has zero prime factors. The factorizations 4 = 2 \times 2 and 6 = 2 \times 3 each have two prime factors. Therefore, for n = 7, the answer is .
The first line contains the number of test cases. Each test case consists of a single integer (1 \leq n < 2^{31} - 1).
For each test case, output a single integer — the largest number between and that has the maximum number of prime factors among all numbers from to .
Example 1