/**************************************************************

     Problem: 2492

     User: rausen

     Language: C++

     Result: Accepted

     Time:2836 ms

     Memory:71184 kb

 ****************************************************************/

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <map>

 using namespace std;

 const int radix = 1e8;

 const int Mx = 1e5;

 const int N = ;

 struct fib {

     int l, x[];

     inline void zero() {

         memset(x, , sizeof(x));

         l = ;

     }

     inline void one() {

         memset(x, , sizeof(x));

         x[] = l = ;

     }

     inline int& operator [] (const int &p) {

         return x[p];

     }

     inline fib operator + (const fib &b) const {

         static fib res;

         static int i;

         res.zero(), res.l = max(l, b.l);

         for (i = ; i < res.l; ++i) {

             res[i] += x[i] + b.x[i];

             res[i + ] = res[i] / radix, res[i] %= radix;

         }

         if (res[res.l]) ++res.l;

         return res;

     }

 } a, b, c;

 char ch[];

 struct edge {

     int next, to, t;

     edge() {}

     edge(int _n, int _to, int _t) : next(_n), to(_to), t(_t) {}

 } e[N];

 int first[N], tot, pos[N], cnt_T;

 inline void add_edge(const int &x, const int &y, const int &t) {

     e[++tot] = edge(first[x], y, t), first[x] = tot;

 }

 inline int find(const int &p, const int &t) {

     static int x;

     for (x = first[p]; x; x = e[x].next)

         if (e[x].t == t) return e[x].to;

     return ;

 }

 #define Pos pos[p]

 inline void trie_insert(char* ch, const int &len, const int &P) {

     static int p, i, t;

     for (p = i = ; i < len; ++i) {

         t = ch[i] - '';

         if (!find(p, t)) {

             add_edge(p, ++cnt_T, t);

             p = cnt_T;

         } else p = find(p, t);

         if (Pos == ) Pos = P + ;

     }

 }

 inline void trie_query(char *ch, const int &len) {

     static int p, i, t;

     for (p = i = ; i < len; ++i) {

         t = ch[i] - '';

         if ((p = find(p, t)) == ) {

             puts("-1");

             return;

         }

     }

     printf("%d\n", Pos - );

 }

 #undef Pos

 int main() {

     int i, j, tot_len, tmp, len, Q, icase;

     a.one(), b.one();

     trie_insert("", , );

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

         c = b + a, a = b, b = c, len = c.l;

         tot_len = sprintf(ch, "%d", c[len - ]);

         for (j = ; j <= len; ++j) {

             tmp = sprintf(ch + tot_len, "%08d", c[len - j]);

             if ((tot_len += tmp) >= ) break;

         }

         tot_len = min(tot_len, );

     trie_insert(ch, tot_len, i);

     }

     scanf("%d", &Q);

     for (icase = ; icase <= Q; ++icase) {

         scanf("%s", ch);

         len = strlen(ch);

         printf("Case #%d: ", icase);

         trie_query(ch, len);

     }

     return ;

 }