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
For centuries it had been assumed that there was no way to compute the -th digit of without calculating all of the preceding digits, but the discovery of this formula laid out the possibility. This problem asks you to calculate the hexadecimal digit of immediately after the hexadecimal point. For example, the hexadecimal format of is and the -st digit is , the -th one is and the -th one is .
输入格式
The first line of input contains an integer () which is the total number of test cases. Each of the following lines contains an integer ().
输出格式
For each test case, output a single line beginning with the sign of the test case. Then output the integer , and the answer which should be a character in as a hexadecimal number.
样例
样例输入 1
5
1
11
111
1111
11111
样例输出 1
Case #1: 1 2
Case #2: 11 A
Case #3: 111 D
Case #4: 1111 A
Case #5: 11111 E
