Для натурального числа \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}.