Divisors of 2#3672
For a positive integer , let be the smallest positive integer having exactly divisors. For example, f(1) = 1, f(5) = 16, f(6) = 12.
For a given non-negative integer , you need to find f(2^k) \bmod 99999640000243.
The first line of the input file contains an integer (1 \le T \le 10^5) - the number of test cases. Each of the following lines contain an integer (1 \le k \le 10^{18}).
For each from the input file, output f(2^k) \bmod 99999640000243. Each value must be on the separate line.
Example 1