dp[pos][n]表示值<=n的 长度为pos位的数的个数
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
int dp[20][200000],num[20];
int f(int n)
{
int tmp,cnt;
cnt=0;tmp=0;
while(n)
{
tmp+=(n%10)*(1<<cnt);
cnt++;
n/=10;
}
return tmp;
}
int dfs(int n,int pos,int flag)
{
if(n<0) return 0;
if(pos==-1) return n>=0;
if(!flag&&dp[pos][n]!=-1) return dp[pos][n];
int ans,p,i;
if(flag) p=num[pos];
else p=9;
ans=0;
for(i=0;i<=p;i++)
ans+=dfs(n-i*(1<<pos),pos-1,flag&&i==p);
if(!flag) dp[pos][n]=ans;
return ans;
}
int main()
{
int t,a,b,l,fa,cnt=0;
memset(dp,-1,sizeof dp);
scanf("%d",&t);
while(t--)
{
cnt++;
scanf("%d%d",&a,&b);
fa=f(a);
l=0;
while(b)
{
num[l]=b%10;
l++;
b/=10;
}
printf("Case #%d: %d\n",cnt,dfs(fa,l-1,1));
}
return 0;
}