Some days ago Leeana Learned about Fibonacci Number, and then her uncle gave her a task: find the last two digits of Nth Fibonacci number.

The Fibonacci number sequence are: 0 1 1 2 3 5 8 13 21... (0 based counting)

Note: always print two digits, even if the Nth Fibonacci number is only a signle digit.

Input

The first line of input contains an integer T <= 100 denoting the number of test cases. Then T test cases follow. Each test case contains an integer N <= 10^18.

Output

Print in each line of test case ("Case x: ans") where x is the case number, and ans is the required answer to this problem. See sample input/output for exact format.

Example

Input:
3
0
7
10

Output:
Case 1: 00
Case 2: 13
Case 3: 55