#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char a[100],b[100],c[100],t[100];
typedef struct s
{
	struct s * child[10];
	int id;
}node,*Node;
Node root;
void add(char a[],char b[],char c[])  
{  
    int len1,len2,i,j,t[10000],max,k=0;  
    len1=strlen(a);  
    len2=strlen(b);  
    i=len1-1;  
    j=len2-1;  
    memset(t,sizeof(t));  
    while(i>=0||j>=0)  
    {  
        if(i<0&&j>=0)  
            t[k]+=b[j]-'0';  
        else  
            if(j<0&&i>=0)  
                t[k]+=a[i]-'0';  
            else  
            {  
                t[k]+=a[i]-'0'+b[j]-'0';  
            }  
        k++;  
        t[k]+=t[k-1]/10;  
        t[k-1]%=10;  
        if(t[k])  
            max=k;  
        else  
            max=k-1;  
        i--;  
        j--;  
    }  
    for(i=max;i>=0;i--)  
        c[max-i]=t[i]+'0';  
    c[max+1]='';  
    //return c;  
}  
char str[3][100];
void insert(char *s,int id)
{
	Node cur,newnode;
	int i,now,len;
	len=strlen(s);
	cur=root;
	//int i;
	for(i=0;i<len&&i<41;i++)
	{
		now=s[i]-'0';
		if(cur->child[now]!=NULL)
		{
			cur=cur->child[now];
		}
		else
		{
			newnode=(Node)calloc(1,sizeof(node));
			cur->child[now]=newnode;
			cur=cur->child[now];
			cur->id=id;
		}
	}
}
int seach(char *s)
{
	int len=strlen(s),i;
	Node cur;
	cur=root;
	for(i=0;i<len;i++)
	{
		int now=s[i]-'0';
		if(cur->child[now]==NULL)
			break;
		cur=cur->child[now];
	}
	if(i<len)
		return -1;
	return cur->id;
}
void fun()
{
	strcpy(a,"1");
	insert(a,0);
	strcpy(b,"1");
	insert(b,1);
	for(int i=2;i<100000;i++)
	{
		int len1=strlen(a);
		int len2=strlen(b);
		if(len2>60)
		{
			b[len2-1]=0;
			a[len1-1]=0;
		}
		add(a,b,t);
		insert(t,i);
		strcpy(a,b);
		strcpy(b,t);
	//	if(i<30)
	//		printf("%sn",t);
	}
}
int main()
{
	int t,c=0;
	root=(Node)calloc(1,sizeof(node));
	fun();
	scanf("%d",&t);
	while(t--)
	{
		char temp[50];
		scanf("%s",temp);
		printf("Case #%d: ",++c);
		printf("%dn",seach(temp));
	}
}