记录编号	32570	评测结果	AAAAAAAAAA
题目名称	607.产生01串	最终得分	100
用户昵称	Des.	是否通过	通过
代码语言	Pascal	运行时间	0.099 s
提交时间	2011-11-07 12:34:47	内存使用	0.12 MiB

program infinit;
var a:array[1..100,0..1]of int64;
    f:Array[0..100]of int64;
    t,k,m,n:longint;
    s,i,j,x,y:int64;
begin
assign(input,'infinit.in' );
reset(input);
assign(output,'infinit.out');
rewrite(output);
readln(n);
a[1,0]:=0;
a[1,1]:=1;
f[0]:=1;
f[1]:=1;
for t:=2 to 91 do
  begin
    a[t,0]:=a[t-1,1];
    a[t,1]:=a[t-1,0]+a[t-1,1];
    f[t]:=f[t-1]+f[t-2];
  end;
for t:=1 to n do
  begin
    readln(i,j);
    x:=0;
    y:=0;
    dec(i);
    for k:=1 to 92 do
      if f[k]>i then break;
    dec(k);
    if i>0 then
    repeat
      if f[k]<=i then
        begin
          i:=i-f[k];
          x:=x+a[k,1];
        end;
      dec(k);
    until i=0;
    for k:=1 to 92 do
      if f[k]>j then break;
    dec(k);
    if j>0 then
    repeat
      if f[k]<=j then
        begin
          j:=j-f[k];
          y:=y+a[k,1];
        end;
      dec(k);
    until j=0;
    writeln(y-x);
  end;
close(output);
end.