Little Rumon is an enthusiast lad. One day while he was exploring the basement of their house for old garbage to find out any usable tool, he suddenly found an interesting device which had a display and a button. He found that if the button is pressed for t seconds, t random binary digits are displayed.

It always had two property:

1. The binary number generated has no leading zeros.
2. There are no consecutive 1’s in the number.

Suppose, t = 4, then the possible outcomes are 1000, 1001, 1010.

Rumon instantly rushed to his elder brother Shovon to show him what he had found. After testing the device, Shovon also got interested because the device was generating some number that is equal to the decimal representation of some Cricket South African player’s jersey number.

As for example, the device generated 1, 10001 and 1000 respectively which decimal representations are 1, 17 and 8, which are Hashim Amla, AB de Villiers and Dale Steyn’s jersey numbers respectively.

They started to call such numbers “Binary Protean Number”.

By the time, Rumon wondered if he writes down a binary protean number on a paper, what will be it’s position in all possible binary protean number’s sorted list.

Shovon wanted to write a C program to answer Rumon’s question, but then he thought that there is an upcoming Programming Contest arranged by “Programming Problem in Bengali” Facebook group. So he decided to set it as a programming problem.

Now it’s your job to help little Rumon.

Formally, given K’th Binary Protean Number, you have to find the value of K.

Input

The first line of the input file contains an integer T. 1 <= T <= 75000. Then follows T cases. Every case consists of one line. The line contains a Binary Protean Number. It has no leading zeros and no consecutive ones in it. If the length of the Binary Protean Number is L then 1 <= L <= 90.

Output

For every case, you should output a line containing the case number and the value of K. The output format is: Case X: K Where X is the case number. It is guaranteed that K will fit in 64 bit long long integer.

See Sample input/output section for better understanding.

Sample

Input:
3
1
100
1010

Output:
Case 1: 1
Case 2: 3
Case 3: 7