Problems
Делители 2
Делители 2
Для натурального числа \textbf{x} обозначим через \textbf{f(x)} наименьшее натуральное число, имеющее ровно \textbf{x} делителей. Например, \textbf{f(1) = 1}, \textbf{f(5) = 16}, \textbf{f(6) = 12}.
Для данного целого неотрицательного числа \textbf{k} необходимо найти \textbf{f(2^k) mod 99999640000243}.
\InputFile
В первой строке входного файла задано натуральное число \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10^5}) - количество тестов. В каждой из последующих \textbf{T} строк задано целое число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^18}).
\OutputFile
Для каждого \textbf{k} из входного файла выведите в отдельной строке число \textbf{f(2^k) mod 99999640000243}.
Input example #1
5 0 1 2 3 4
Output example #1
1 2 6 24 120