Program coin34;
Const fi='';
Var A,X,Y:array[1..34] of longint;
F:array[0..50000] of longint;
tong,dem,V,max:int64;
T:longint;
Procedure init;
Var i,j:longint;
Begin
A[1]:=2;A[2]:=3;
For i:=3 to 34 do A[i]:=A[i-1]+A[i-2];
for i:=1 to 20 do X[i]:=A[i];
For i:=1 to 14 do Y[i]:=A[i+20];
end;
Procedure try1;
Var j,i:longint;
Begin
For i:=1 to 20 do
Begin
for j:=50000 downto 0 do
if (F[j]<>0) or (j=0) then
if F[j+X[i]]<=F[j] then F[j+X[i]]:=F[j]+1;
end;
end;
Procedure try2;
Var i,j,so,R,dem:longint;
Begin
For i:=0 to 16383 do
Begin
tong:=0; dem:=0;
so:=i;
For j:=1 to 14 do
Begin
r:=so mod 2;
so:=so shr 1;
if r=1 then
Begin
dem:=dem+1;
tong:=tong+y[j];
end;
end;
if (V-tong<50000) and (tong<V) then
if (F[V-tong]<>0) and (f[V-tong]+dem>max) then max:=F[v-tong];
end;
end;
Procedure process;
Var i:longint; g:text;
Begin
Assign(g,fi); Reset(g);
Readln(g,T);
fillchar(f,sizeof(f),0);
try1;
For i:=1 to T do
Begin
dem:=0;
tong:=0;
max:=0;
readln(g,v);
dem:=0; tong:=0;
try2;
write('Case #',i,': ');
if max<>0 then
writeln(max)
else writeln('-1');
end;
Close(g);
end;
Begin
init;
process;
end.
Const fi='';
Var A,X,Y:array[1..34] of longint;
F:array[0..50000] of longint;
tong,dem,V,max:int64;
T:longint;
Procedure init;
Var i,j:longint;
Begin
A[1]:=2;A[2]:=3;
For i:=3 to 34 do A[i]:=A[i-1]+A[i-2];
for i:=1 to 20 do X[i]:=A[i];
For i:=1 to 14 do Y[i]:=A[i+20];
end;
Procedure try1;
Var j,i:longint;
Begin
For i:=1 to 20 do
Begin
for j:=50000 downto 0 do
if (F[j]<>0) or (j=0) then
if F[j+X[i]]<=F[j] then F[j+X[i]]:=F[j]+1;
end;
end;
Procedure try2;
Var i,j,so,R,dem:longint;
Begin
For i:=0 to 16383 do
Begin
tong:=0; dem:=0;
so:=i;
For j:=1 to 14 do
Begin
r:=so mod 2;
so:=so shr 1;
if r=1 then
Begin
dem:=dem+1;
tong:=tong+y[j];
end;
end;
if (V-tong<50000) and (tong<V) then
if (F[V-tong]<>0) and (f[V-tong]+dem>max) then max:=F[v-tong];
end;
end;
Procedure process;
Var i:longint; g:text;
Begin
Assign(g,fi); Reset(g);
Readln(g,T);
fillchar(f,sizeof(f),0);
try1;
For i:=1 to T do
Begin
dem:=0;
tong:=0;
max:=0;
readln(g,v);
dem:=0; tong:=0;
try2;
write('Case #',i,': ');
if max<>0 then
writeln(max)
else writeln('-1');
end;
Close(g);
end;
Begin
init;
process;
end.