Найдите число от 1 до n включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выберите максимальное из них.

Например, найдем розложение на простые множнители чисел от 1 до 7. Числа 2, 3, 5 и 7 простые, в их разложении по одному множителю. В разложении числа 1 ноль простых множиителей. В разложении чисел 4 = 2 * 2 и 6 = 2 * З по два простых множителя. Значит, ответом к задаче для n = 7 есть число 6.

Input

В первой строке находится количество тестов. Каждый тест состоит из одного целого числа n (1 ≤ n < 231 - 1).

Output

Для каждого теста выведите одну строку, которая будет содержать одно целое число - наибольшее число от 1 до n, количество простых множителей которого максимально, среди всех чисел от 1 до n.