#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 10005
#define MAXN 100005
#define mod 100000000
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int a,b,fac[10];
int dp[10][10][5500],sum[10][10][5500];

void solve()
{
    int i,j,t=0,u,v;
    for(i=9;i>=1;i--)
    {
        t+=((a/fac[i-1])%10)*(1<<i-1);
    }
    a=t;
    ans=0;
    for(i=9;i>=1;i--)
    {
        u=(b/fac[i-1])%10;
        for(j=0;j<u;j++)
        {
            ans+=sum[i][j][a];
        }
        a-=u*(1<<i-1);
        if(a<0) return ;
    }
    ans++;
}
int main()
{
    int i,j,k,p,q,t,test=0;
    fac[0]=1;
    for(i=1;i<10;i++)
    {
        fac[i]=fac[i-1]*10;
    }
    dp[0][0][0]=1;
    for(i=1;i<=9;i++)
    {
        for(j=0;j<=9;j++)
        {
            for(k=0;k<=5000;k++)
            {
                t=0;
                for(p=0;p<=9;p++)
                {
                    if((k-(1<<i-1)*j)>=0) t+=dp[i-1][p][k-(1<<i-1)*j];
                }
                dp[i][j][k]=t;
                if(k>0) sum[i][j][k]=sum[i][j][k-1]+t;
                else sum[i][j][k]=t;
            }
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        solve();
        printf("Case #%d: %d\n",++test,ans);
    }
    return 0;
}
/*
3
0 100
1 10
5 100
Case #1: 1
Case #2: 2
Case #3: 13
*/