Знайдіть число від 1 до n включно таке, що у розкладі його на прості множники кількість множників максимальна. Якщо таких чисел декілька, виберіть максимальне із них.

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

Вхідні дані

У першому рядку знаходиться кількість тестів. Кожен набір складається з одного цілого числа n (1 ≤ n < 231 - 1).

Вихідні дані

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