P17065 [ICPC 2017 Shenyang R] BBP Formula

In 1995, Simon Plouffe discovered a special summation style for some constants. Two years later, together with the paper of Bailey and Borwein 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} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right) $$ For centuries it had been assumed that there was no way to compute the $n$-th digit of $\pi$ without calculating all of 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 hexadecimal format of $\pi$ is $3.243F6A8885A308D313198A2E \cdots$ and the $1$-st digit is $2$, the $11$-th one is $A$ and the $15$-th one is $D$.

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

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