Ocarth

Ocarth is a planet nearly identical to our Earth. It's inhabited by Ocarthling, and they are very similar to us, Earthling. The only thing which is not the same is the number system used by Ocarthlings. Instead of the usual decimal number system (base-10), Ocarthlings use octal number system (base-8). This is because Ocarthlings only have 8 fingers on their hands.

Apparently, there was also a programming contest being held in Ocarth, and this was one of the problem:

Given an integer K, find the Kth digit which appears on a string formed by concatenating all integers from 1. For example, let K be 11, then the K = 11th digit is 0.

1234567101112131415161720212223

You should output the integer in which the Kth digit is located, and surround the Kth digit with brackets. So, the output for K = 11 is 1(0) as the integer is 10. If K = 34, then the output is (2)2.

Input

Input begins with an integer T (1 ≤ T ≤ 144) denoting the number of cases. The next N lines, each contains an integer K (1 ≤ K ≤ 16715312000).

Output

For each case, output "Case #X: Y" in a line, where X is the case number (starts from 1), and Y is the output for the respective input.

Examples

inputExample #1
7
1
3
6
12
17
25
34
output
Case #1: (1)
Case #2: (3)
Case #3: (6)
Case #4: (1)1
Case #5: 1(3)
Case #6: 1(6)
Case #7: (2)2 

inputExample #2
11
1
2
3
4
5
6
7
10
11
output
Case #1: (1)
Case #2: (2)
Case #3: (3)
Case #4: (4)
Case #5: (5)
Case #6: (6)
Case #7: (7)
Case #10: (1)0
Case #11: 1(0)

As you might have noticed, ALL the integers in this problem are in OCTAL (base 8). Your task is to write the code to emulate the solution to this problem. Note: You live on the Earth.


End of Problem