FIBMYSTRY - SOME MYSTERY HAPPENED

no tags 

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

hide comments
Francky: 2017-02-08 17:43:22

To be moved ASAP in tutorial. A psetter should know standards for classical problems, and in particular not to set already existing tasks (or way too near).

[Rampage] Blue.Mary: 2017-02-08 16:56:20

This shoule be put into tutorial section because there exists large number of (directly) matrix multiplication problem in SPOJ classical section.


Added by:RaYHan
Date:2017-02-08
Time limit:0.100s-0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem