Problem Description

In 1995, Simon Plouffe discovered a special summation style for some constants. Two year later, together with the paper of Bailey and Borwien published, this summation style was named as the Bailey-Borwein-Plouffe formula.Meanwhile a sensational formula appeared. That is
$$\pi = \sum_{k=0}^{\infty }\frac{1}{16^{k}}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})$$
For centuries it had been assumed that there was no way to compute the n-th digit of $\pi$ without calculating allof the preceding n - 1 digits, but the discovery of this formula laid out the possibility. This problem asks you to
calculate the hexadecimal digit n of $\pi$ immediately after the hexadecimal point. For example, the hexadecimalformat of n is 3.243F6A8885A308D313198A2E ... and the 1-st digit is 2, the 11-th one is A and the 15-th one is D.

Input

The first line of input contains an integer T (1 ≤ T ≤ 32) which is the total number of test cases.
Each of the following lines contains an integer n (1 ≤ n ≤ 100000).

Output

For each test case, output a single line beginning with the sign of the test case. Then output the integer n, andthe answer which should be a character in {0, 1, · · · , 9, A, B, C, D, E, F} as a hexadecimal number

5
1
11
111
1111
11111

Case #1: 1 2
Case #2: 11 A
Case #3: 111 D
Case #4: 1111 A
Case #5: 11111 E