SP27497 BINPRNUM - Binary Protean Number

小 Rumon 是个充满好奇心的年轻人。有一天，他在家里的地下室翻找旧物，希望能找到一些可用的工具，却意外发现了一个有趣的装置。这个装置上有一个显示屏和一个按钮。他发现在按住按钮 $t$ 秒时，屏幕会显示出 $t$ 个随机的二进制数字。 这个装置总是遵循两个特定的规则： 1. 生成的二进制数没有前导零。 2. 数字中不存在连续的 1。 举个例子，当 $t = 4$ 时，可能出现的结果有 1000, 1001 和 1010。 Rumon 立刻跑去找他的哥哥 Shovon，并兴奋地展示他的发现。在测试这个装置之后，Shovon 也很感兴趣，因为这个装置生成的数字正好对应了一些南非板球运动员球衣号码的十进制形式。 例如，装置生成了 1, 10001 和 1000，它们对应的十进制值分别是 1, 17 和 8，这些正是 Hashim Amla, AB de Villiers 和 Dale Steyn 的球衣号码。 他们开始把这样的数字称为“二进制 Protean 数”。 后来，Rumon 想知道，如果他在纸上写下一个二进制 Protean 数，这个数在所有可能的二进制 Protean 数的排序列表中处于什么位置。 Shovon 本想写一个 C 程序来回答 Rumon 的问题，但随即想到即将到来的由“Programming Problem in Bengali”Facebook 小组组织的编程比赛，他决定将这个问题设为竞赛题目。 现在，你的任务是帮助小 Rumon 解决这个问题。 具体来说，给定一个二进制 Protean 数，找出它在所有可能的二进制 Protean 数中的顺序，即求出他的第 $K$ 位。

第一行输入一个整数 $T$，表示测试用例的数量 ($1 \le T \le 75000$)。接下来是 $T$ 组测试数据，每组数据占一行，包含一个二进制 Protean 数。这个数没有前导零，也没有连续的 1。如果该数的长度为 $L$，则满足 $1 \le L \le 90$。

对于每组测试数据，输出一行，格式为：`Case X: K`，其中 $X$ 是测试用例的编号，$K$ 是求得的次序值。保证 $K$ 在 64 位长整型范围内。

- $1 \le T \le 75000$ - $1 \le L \le 90$ **本翻译由 AI 自动生成**