Делители 2

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

Для данного целого неотрицательного числа k необходимо найти f(2^k) mod 99999640000243.

Input

В первой строке входного файла задано натуральное число T (1 ≤ T ≤ 10^5) - количество тестов. В каждой из последующих T строк задано целое число k (1 ≤ k ≤ 10^18).

Output

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

Examples