#include<fstream>
using namespace std;
ifstream cin("infinit.in");
ofstream cout("infinit.out");
long long Q,a,b,ge[94],wei[94],i,j,yi;
long long num(long long x,int p)
{
	if(wei[p]==x)
		return ge[p];
	if(wei[p]>=x)
		return num(x,p-1);
	else
		return (ge[p]+num(x-wei[p],p-1));
}
int main()
{
	cin>>Q;
	ge[1]=1;
	ge[2]=1;
	wei[1]=1;
	wei[2]=2;
	for(i=3;i<94;i++)
	{
		ge[i]=ge[i-1]+ge[i-2];
		wei[i]=wei[i-1]+wei[i-2];
	}
	for(i=0;i<Q;i++)
	{
		cin>>a>>b;
		yi=num(b,93);
		yi=yi-num(a-1,93);
		cout<<yi<<endl;
	}
	return 0;
}