#include <cstdio>
using namespace std;

struct boolean
{
	bool b[10000000];
};

boolean a={0},b={0},c={0};
int la,lb,lc,s[10000000]={0};

int main(void)
{
	freopen("infinit.in","r",stdin);
	freopen("infinit.out","w",stdout);
	int i,q,inf[5000][2],maxnum=0;
	scanf("%d\n",&q);
	for (i=0;i<q;i++)
	{
		scanf("%d %d\n",&inf[i][0],&inf[i][1]);
		if (inf[i][1]>maxnum)
			maxnum=inf[i][1];
	}
	la=1;
	lb=2;
	lc=3;
	a.b[1]=1;
	b.b[1]=1;
	b.b[2]=0;
	c.b[1]=1;
	c.b[2]=0;
	c.b[3]=1;
	while (lc<maxnum)
	{
		la=lb;
		lb=lc;
		lc=la+lb;
		a=b;
		b=c;
		for (i=1;i<=la;i++)
			c.b[lb+i]=a.b[i];
		
	}
	for (i=1;i<=maxnum;i++)
		s[i]=s[i-1]+c.b[i];
	for (i=0;i<q;i++)
	{
		if (inf[i][1]!=inf[i][0])
			printf("%d\n",s[inf[i][1]]-s[inf[i][0]]);
		else
			printf("%d\n",int(c.b[inf[i][1]]));
	}
	fclose(stdin);
	fclose(stdout);
	return(0);
}