program infinit;
var
  i,j,l,n,q,a,b,num,t:longint;
  s,p:array[1..10000000]of byte;
procedure init;
begin
  assign(input,'infinit.in');
  reset(input);
  assign(output,'infinit.out');
  rewrite(output);
  read(q);
  s[1]:=1;
  num:=1
end;

procedure data;
begin
  i:=1;  j:=0;
  repeat
    if s[i]=0 then
    begin
      inc(j);
      p[j]:=1
    end;
    if s[i]=1 then
    begin
      inc(j); p[j]:=1;
      inc(j); p[j]:=0
    end;
    inc(i)
  until i>num;
  num:=j;
  for i:=1 to num do
    s[i]:=p[i]
end;

procedure count;
begin
  t:=0;
  for i:=a to b do
    if p[i]=1 then inc(t)
end;

procedure main;
begin
  for l:=1 to q do
  begin
    readln(a,b);
    while b>num do data;
    count;
    writeln(t)
  end;
  close(input);
  close(output)
end;

begin
  init;
  main
end.