/*
 
Tm : struct tap thu nhat ( 20 phan tu )
  Tm.m : gia tri cua 1 to hop
  Tm.xm : so phan tu tao ra tong Tm.m do
Tn : struc tap thu hai ( 14 phan tu )
  Tm.n : gia tri cua 1 to hop
  Tm.xn : so phan tu tao ra tong Tn.n do
 
*/
 
#define T 34
#define T1 20
#define T2 14
inline void init()
  a[0] = 2;
  a[1] = 3;
  a[2] = 5;
  FOR(i,3,T)
    a[i] = a[i-1] + a[i-2] + a[i-3];
 
  FOR(i,0,1<<T1){// tap 1 : co 2^20 trang thai
    FOR(j,0,T1){// gom 20 phan tu dau tien
      if(i & (1<<j)){// neu bit j trong i la 1
        Tm[i].m += a[j];
        Tm[i].xm++;// so dong xu tao ra tong m[i] tang len 1
      }
    }
    
  }
  
  FOR(i,0,1<<T2) {// tap 2 : co 2^14 trang thai
    FOR(j,T1,T) {// gom 14 phan tu tiep theo
      if(i & (1<<(j-T1))){
        Tn[i].n += a[j];
        Tn[i].xn++; // so dong xu tao ra tong n[i] tang len 1
      }
    }
  }
}

 
const fi='';
      fo='';
type tong=array[1..1048576] of longint;
     tong2=array[1..1048576] of byte;
var f1,f2:text;
    sum,sum2:tong;
    count,count2:tong2;
    a:array[1..34] of longint;
    x,i,s,sl,sl2,dem,kq,n,t:longint;
 
function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;
procedure sinh;INLINE;
begin
 inc(sl);
 sum[sl]:=s;
 count[sl]:=dem;
end;
procedure tryS(i,k:byte);
var j:byte;
begin
 for j:=0 to 1 do
  begin
   s:=s+a[i]*j;
   if j=1 then inc(dem);
   if i=k then sinh else tryS(i+1,k);
   if j=1 then dec(dem);
   s:=s-a[i]*j;
  end;
end;
procedure swap1(var a,b:longint);
var tmp:longint;
begin
 tmp:=a;
 a:=b;
 b:=tmp;
end;
procedure swap2(var a,b:byte);
var tmp:byte;
begin
 tmp:=a;
 a:=b;
 b:=tmp;
end;
procedure quicksort(l,h:longint);  INLINE;
var x:longint;
    i,j:longint;
begin
 i:=l;
 j:=h;
 x:=sum2[l+random(h-l+1)];
 repeat
  while sum2[i]<x do inc(i);
  while sum2[j]>x do dec(j);
  if i<=j then
    begin
     swap1(sum2[i],sum2[j]);
     swap2(count2[i],count2[j]);
     inc(i);
     dec(j);
    end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
end;
procedure process;
begin
 a[1]:=2;
 a[2]:=3;
 a[3]:=5;
 for i:=4 to 34 do begin a[i]:=a[i-3]+a[i-2]+a[i-1];end;
 sl:=0;
 tryS(1,20);
 sum2:=sum;
 count2:=count;
 sl2:=sl;
 quicksort(1,sl2);
 fillchar(sum,sizeof(sum),0);
 fillchar(count,sizeof(count),0);
 sl:=0;
 tryS(21,34);
end;
procedure tknp;   
var dau,cuoi,mid,k,node:longint;
begin
 kq:=-1;
 for i:=1 to sl do
  begin
   k:=x-sum[i];
   dau:=1;
   cuoi:=sl2;
   while dau<=cuoi do
    begin
       mid:=(dau+cuoi)div 2;
       if sum2[mid]=k then
          begin
            kq:=max(kq,count[i]+count2[mid]);
            node:=mid-1;
               while sum2[node]=k do
                begin
                   kq:=max(kq,count[i]+count2[node]);
                   dec(node);
                   if node =0 then break;
                end;
             node:=mid+1;
               while sum2[node]=k do
                begin
                  kq:=max(kq,count[i]+count2[node]);
                  inc(node);
                  if node=sl2+1 then break;
                end;
            break;
          end
       else if sum2[mid]>k then cuoi:=mid-1
       else dau:=mid+1;
      end;
   end;
end;
BEGIN
 assign(f1,fi);
 reset(f1);
 readln(f1,n);
 assign(f2,fo);
 rewrite(f2);
 process;
 for t:=1 to n do
  begin
   readln(f1,x);
   tknp;
   writeln(f2,'Case #',t,': ',kq);
  end;
 close(f1);
 close(f2);
END.
 

{$mode ObjFpc} {$-R,-Q} {$inline on}
const
      finp    =     '';
      fout    =     '';
var
      fi,fo   :     text;
      X       :     Array[1..35] of qword;
      S1,S2   :     qword;
      St2,T   :     qword;
      T1      :     Array[0..1048577,1..2] of qword;
      T2      :     Array[1..16385,1..2] of qword;
      Q       :     qword;
      max1,max2 :   longint;
//
Procedure OpenFile;
begin
      Assign(fi,finp);
      reset(fi);
      Assign(fo,fout);
      Rewrite(fo);
end;
//
procedure CloseFile;
begin
      Close(fi);
      Close(fo);
end;
//
Procedure Back1(i:byte);
var
      j       :     byte;
begin
      if i=1 then max1:=0;
      for j:=0 to 1 do
        begin
          s1:=s1+j*X[i];
          if j=1 then inc(max1);
          if i=20 then
            begin
              inc(T1[s1][1]);
              if T1[s1][2]=0 then T1[s1][2]:=max1
              else if T1[s1][2]<max1 then T1[s1][2]:=max1;
            end
          else
            Back1(i+1);
          s1:=s1-j*X[i];
          if j=1 then dec(max1);
        end;
end;
//
Procedure Back2(i:byte);
var
      j       :     byte;
begin
      if i=21 then max2:=0;
      for j:=0 to 1 do
        begin
          s2:=s2+j*X[i];
          if j=1 then inc(max2);
          if i=34 then
            begin
              inc(St2);
              T2[St2][1]:=s2;
              T2[St2][2]:=max2;
            end
          else
            Back2(i+1);
          s2:=s2-j*X[i];
          if j=1 then dec(max2);
        end;
end;
//
Procedure Solve(j:longint);
var
      i,res   :     longint;
begin
      readln(fi,Q);
      res:=0;
      for i:=1 to St2 do
        if (Q-T2[i][1]>=0) and (Q-T2[i][1]<=1048577) then
          if T1[Q-T2[i][1]][2]+T2[i][2]>res then res:=T1[Q-T2[i][1]][2]+T2[i][2];
      if res=0 then res:=-1;
      writeln(fo,'Case #',j,': ',res);
end;
//
Procedure Process;
var
      i       :     integer;
begin
      X[1]:=2;
      X[2]:=3;
      X[3]:=5;
      for i:=4 to 34 do
        X[i]:=X[i-3]+X[i-2]+X[i-1];
      S1:=0;S2:=0;St2:=0;
      Back1(1);
      Back2(21);
      readln(fi,T);
      for i:=1 to T do
        Solve(i);
end;
//
begin
      OpenFile;
      Process;
      CloseFile;
end.