program sad;
var
b,a:array[1..8000] of longint;

f,j,i,h,t,d,p,q:longint;
begin
t:=1;
while t<>0 do
begin
 d:=d+1;
 readln(t);
 a[d]:=t;
end;

b[1]:=1;
b[2]:=1;
for i:=1 to d-1 do
begin
 f:=0;
 for j:=3 to a[i] do
 begin

 if j<8001 then
 begin
 p:=j div 2;
 q:=j mod 2;
 if q=0 then
 begin
  b[j]:=b[p];
 end;
 if q=1 then
 begin
  b[j]:=b[p]+b[p+1];
 end;
 end;
 end;

 if a[i]<8001 then
 begin
 for h:=1 to a[i] do
 begin
 if b[h]>f then
 begin
 f:=b[h];
 end;
 end;
 writeln(f);
 end;
end;
readln;
end.

> program sad;
> var
> b,a:array[1..8000] of longint;
>
> f,j,i,h,t,d,p,q:longint;
> begin
> t:=1;
> while t<>0 do
> begin
>  d:=d+1;
>  readln(t);
>  a[d]:=t;
> end;
>
> b[1]:=1;
> b[2]:=1;
> for i:=1 to d-1 do
> begin
>  f:=0;
>  for j:=3 to a[i] do
>  begin
>
>  if j<8001 then
>  begin
>  p:=j div 2;
>  q:=j mod 2;
>  if q=0 then
>  begin
>   b[j]:=b[p];
>  end;
>  if q=1 then
>  begin
>   b[j]:=b[p]+b[p+1];
>  end;
>  end;
>  end;
>
>  if a[i]<8001 then
>  begin
>  for h:=1 to a[i] do
>  begin
>  if b[h]>f then
>  begin
>  f:=b[h];
>  end;
>  end;
>  writeln(f);
>  end;
> end;
> readln;
> end.
>
>