记录编号	32943	评测结果	AAAAAAAAAA
题目名称	产生01串	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.192 s
提交时间	2011-11-08 20:24:28	内存使用	0.27 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
unsigned long long F[95];
unsigned long long L[95];

unsigned long long Getm(unsigned long long  x)
{
	int i1;
	unsigned long long getm=0;
	while(x!=0)
	{
		for(i1=1;i1<=92;i1++)
		{
			if(L[i1]>x)
			{
				getm+=F[i1-1];
				x-=L[i1-1];
				break;
			}
		}
	}
	return getm;
}

int main()
{
	freopen("infinit.in","r",stdin);
	freopen("infinit.out","w",stdout);
	
	F[0]=0;
	F[1]=1,L[1]=1;
	F[2]=1,L[2]=2;
	for (int i=3;i<=92;i++)
	{
		F[i]=F[i-1]+F[i-2];
		L[i]=L[i-1]+L[i-2];
	}
	int N;
	scanf("%d\n",&N);
	for (int i=1;i<=N;i++)
	{
		unsigned long long a,b;
		cin>>a>>b;
		a--;
		cout<<Getm(b)-Getm(a)<<endl;
	}
	return 0;
}