const maxfactor=100000;var t,x,y,i,newp,k,l:longint; sieve:array[1..100000] of boolean; a:array[1..10000] of longint; s,num,q:array[1..100000] of longint;begin s[1]:=0; fillchar(sieve,sizeof(sieve),true); for i:=2 to maxfactor do if sieve[i] then begin newp:=i+i; while newp<=maxfactor do begin sieve[newp]:=false; newp:=newp+i; end; end; for i:=2 to maxfactor do if sieve[i] then begin k:=k+1;a[k]:=i end; s[2]:=2;s[3]:=3; for i:=4 to maxfactor do begin k:=0;newp:=i; if newp mod (newp div 2)=0 then begin s[i]:=s[i div 2];newp:=newp div 2; end; repeat k:=k+1; l:=newp mod a[k]; while l=0 do begin s[i]:=s[i]+a[k]; newp:=newp div a[k]; l:=newp mod a[k]; end; until newp=1; end; for i:=2 to maxfactor do begin num[i]:=num[i-1]+s[i]; if num[i]>1919 then dec(num[i],1919); end; readln(t); for i:=1 to t do begin readln(x,y); q[i]:=num[y]-num[x-1]; if q[i]>1919 then dec(q[i],1919); end; for i:=1 to t do writeln(q[i]);end.