学步园

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>

#define ll long long
#define LL __int64


using namespace std;

vector<int>G[100002];

LL degree[22];//数位记录
LL dp[22][12];//长度为i 的数 模10为j的个数

LL detal(LL n)
{
	LL temp=n;
	LL cnt=0;
	memset(dp,0,sizeof(dp));
	while(temp)
	{
		degree[++cnt]=temp%10;
		temp/=10;
	}
	for(LL i=1;i<=cnt/2;i++)//按高位进行排序，因为得到的degree数组相当于原数倒着的
	{
		LL tmp=degree[i];
		degree[i]=degree[cnt-i+1];
		degree[cnt-i+1]=tmp;
	}
	LL ans=0;
	for(LL i=1;i<=cnt;i++)
	{
		for(LL j=0;j<10;j++)
			for(LL k=0;k<10;k++)
				dp[i][(j+k)%10]+=dp[i-1][j];
		for(LL l=0;l<degree[i];l++)//关键之处

			dp[i][(ans+l)%10]++;
		ans=(ans+degree[i])%10;
	}
	if(!ans)
		dp[cnt][0]++;
	return dp[cnt][0];
}

int main()
{
	int t,Case=0;
	LL a,b;
	cin>>t;
	while(t--)
	{
		scanf("%I64d %I64d",&a,&b);
		printf("Case #%d: %I64d\n",++Case,detal(b)-detal(a-1));
	}
	return 0;
}