PIHEX2

All people use decimal system every day. For all of us the value of Pi is 3.141592653589793238462643383279....

But there is common to use hexadecimal system in programming. The hexadecimal value of Pi is 3.243F6A8885A308D313198A2E037073....

In this problem for given a, You should compute the digit, that appears in hexadecimal representation of Pi at a^th position after comma (for a=0 the answer is '3' - the only digit before comma, for a=1 the answer is '2' - the first digit after comma; see example for clarify).

Input

The first line of input contains single integer t - the number of test cases (1 ≤ t ≤ 20).

The second line of input contains t single-space separated integers a₁, a₂, ..., a_t (0 ≤ a_i ≤ 1000000).

Output

The only line of output should contain t hexadecimal digits (use capital letters A-F), where i^th digit appears in Pi hexadecimal representation at a_i^th position.

Example

Input:

16
0 1 2 3 4 5 6 7 8 9 10 100 1000 10000 100000 1000000

Output:

3243F6A8885C3652