#include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 int p[][];

 int sum[maxn];

 int num[maxn];

 int x, k,cnt;

 void init()  //处于后5位的情况，i是枚举，sum[i]存储的是对应k下的值

 {

     cnt=;

     memset(sum,,sizeof(sum));

     for(int i=;i<;i++)

     {

         int tmp=i;

         while(tmp)

         {

             sum[i]+=p[tmp%][k];

             tmp/=;

         }

         num[cnt++]=sum[i]-i;

     }

     sort(num,num+cnt);

 }

 void solve()  //枚举前5位的值，然后二分查找即可

 {

     ll ans=;

     for(int i=;i<;i++)

     {

         ll tmp=sum[i]-(ll)i*;

         int idx=lower_bound(num,num+cnt,x-tmp)-num;

         while(num[idx]==x-tmp && idx<cnt)

         {

             ans++;

             idx++;

         }

     }

     printf("%lld\n",ans);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     for(int i=;i<;i++)   //预处理i^j的值

     {

         p[i][]=;

         for(int j=;j<;j++)

             p[i][j]=p[i][j-]*i;

     }

     int T;

     int kase=;

     scanf("%d",&T);

     while(T--)

     {

         printf("Case #%d: ",++kase);

         scanf("%d%d",&x,&k);

         init();

         solve();

     }

     return ;

 }