BINPRNUM - Binary Protean Number

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

Added by:Rofi
Date:2016-07-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2017-11-28 07:21:08
Cakewalk after solving NBIN
:D :P
2017-10-04 07:43:49
Excellent adhoc. An hour of hacking and research is always more fun for me than 10 mins of implementing an algorithm from the book.
2016-11-08 11:21:53 Mauro Persano
Problem setter: please fix the problem statement. 10001 is 9, 1000 is 5.

Solvers might want to check out NBIN.
2016-10-09 12:21:31
I think its fib series
2016-10-08 11:07:16
az tutorial section
2016-08-02 14:44:53
Need help ,, time limit exceeded no mater what algo i implement !!!! :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.