PIHEX2  Hexadecimal value of Pi
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 singlespace separated integers a_{1}, a_{2}, ..., a_{t} (0 ≤ a_{i} ≤ 1000000).
Output
The only line of output should contain t hexadecimal digits (use capital letters AF), 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
hide comments
Robert Gerbicz:
20140319 16:53:03
It is good to keep this problem, try to solve the problem without computing the first 1m hex digits of pi !


Francky:
20140319 16:08:58
We are waiting for Robert Gerbicz advice on this problem too. Please. 
Added by:  miodziu 
Date:  20140319 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 