#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define MAX 1e9;

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

const int maxn = ;

struct Node {

    int next[];

    int id;

    Node() {

        for(int i = ; i<; i++) {

            next[i] = -;

        }

        id = -;

    }

};

Node trie[maxn];

int tot = ;

//Node root = trie[tot++];

int idx(char ch) {return ch-'';}

void Insert(char* str, int id) {//字典树插入

//    int u = 0;

//    for(int i = 0; i<strlen(str); i++) {

//        int v = idx(str[i]);//获取字符串当前位置的数字

//        if(trie[u].next[v]==-1) { //如果这个位置是不存在的

//            trie[u].next[v] = tot;

//            u = tot++;

//        } else { //如果这个位置是存在的

//            u = trie[u].next[v];

//        }

//        if(trie[u].id==-1) {

//            trie[u].id = id;

//        }

//    }

    int u = ;

    for(int i = ; i<strlen(str); i++){

        int v = idx(str[i]);

        if(trie[u].next[v]==-){//如果这个位置不存在

            trie[u].next[v] = tot++;

        }

        u = trie[u].next[v];//结点往下走

        if(trie[u].id==-){//保存这个斐波那契数字的id

            trie[u].id = id;

        }

    }

}

int Query(char* str) {

    int u = ;

    for(int i = ; i<strlen(str); i++) {

        int v = idx(str[i]);

        if(trie[u].next[v]==-) { //说明这个前缀不会出现

            return -;

        }

        u = trie[u].next[v];

    }

    return trie[u].id;

}

int fib[][maxn];

int main() {

    FRE();

    int s=,l=;

    char f[];

    Insert("",);

    fib[][] = ;

    fib[][] = ;

    for(int i=; i<; i++) {

        int a=i%, b=(i+)%;//滚动数组，可以手动跑两组斐波那契数字的相加就可以理解了

        for(int k=s; k<l; k++) {

            fib[a][k] = fib[a][k] + fib[b][k];

            if(fib[a][k]>=) { //这位相加可以进位时

                fib[a][k+]++;//下一位加一

                fib[a][k] -= ;//这一位减掉进位的10

                if(k==l-) { //最后一个进位让l加一

                    l++;

                }

            }

        }

        if(l-s>) { //数组中是倒着存这个数的，l-1表示个位开始，s表示最高位

            s++;

        }

        int cnt=;

        for(int k=l-; k>=s&&cnt<; k--){//根据题目提示，只选取前40位即可

            f[cnt++] = fib[a][k]+'';

        }

//        if(i==10)

//            printf("%s\n",f);

        Insert(f,i);

        memset(f,,sizeof(f));

    }

    //cout<<"GG"<<endl;

    char str[];

    int n;

    scanf("%d",&n);

    for(int i=; i<n; i++){

        scanf("%s",str);

        printf("Case #%d: ",i+);

        int ans = Query(str);

        printf("%d\n",ans==- ? -:ans-);

    }

    return ;

}