Дільники 2

Для натурального числа x позначимо через f(x) найменше натуральне число, що має рівно x дільників. Наприклад, f(1) = 1, f(5) = 16, f(6) = 12.

Для заданого цілого невід'ємного числа k потрібно знайти f(2^k) mod 99999640000243.

Вхідні дані

У першому рядку вхідного файлу задано натуральне число T (1 ≤ T ≤ 10^5) — кількість тестів. У кожному з наступних T рядків задано ціле число k (1 ≤ k ≤ 10^18).

Вихідні дані

Для кожного k з вхідного файлу виведіть в окремому рядку число f(2^k) mod 99999640000243.

Приклади