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 it is common to use the hexadecimal system in programming. The hexadecimal value of Pi is 3.243F6A8885A308D313198A2E037073....

In this problem for given value a, you should compute the digit that appears in hexadecimal representation of Pi at the ath 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 to 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 a1, a2 ... at (0 ≤ ai ≤ 1000000).

Output

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

Example

Input:

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

Output:

3243F6A8885C3652

Added by:miodziu
Date:2014-03-19
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-03-19 16:53:03 Robert Gerbicz
It is good to keep this problem, try to solve the problem without computing the first 1m hex digits of pi !

Hint: http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/bbp-alg.pdf

Last edit: 2014-03-19 16:53:25
2014-03-19 16:08:58 Francky
We are waiting for Robert Gerbicz advice on this problem too. Please.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.