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 K

^{th}digit which appears on a string formed by concatenating all integers from 1. For example, let K be 11, then the K = 11^{th}digit is 0.1234567101112131415161720212223You should output the integer in which the K

^{th}digit is located, and surround the K^{th}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

input Example #1 7 1 3 6 12 17 25 34output 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

input Example #2 11 1 2 3 4 5 6 7 10 11output 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*