#include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <string.h>

 #include <algorithm>

 #define LL __int64

 using namespace std;

 LL dp[][<<][];

 LL aa,bb;

 int a[],k;

 /*这道题的难点就在于DP的状态表示了，确实是这样的。DP【pos】【state】【K】,pos表示当前的数位，state表示当前的LIS的状态，K

 表示要求的K长度。那个DFS就不解释了，都成模板了。而对于state的转移，是用二进制表示当前状态，因为最长的

 序列就是0~9十个数表示，所以有十位的二进制。例如12456的上升序列，下一次出现3，则可表示为12356，至于转移，要联系nlogn解法的

 LIS来看了 */

 int getnews(int x,int s){

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

         if(s&(<<i))return (s^(<<i))|(<<x);

     return s|(<<x);

 }

 int getnum(int s){

     int ret=;

     while(s)

     {

         if(s&)ret++;

         s>>=;

     }

     return ret;

 }

 LL dfs(int len,int st,bool zero,bool flag){

     if(len==) return getnum(st)==k;

     if(!flag&&dp[len][st][k]!=-)

     return dp[len][st][k];

     int en=flag?a[len]:;

     LL ans=;

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

         ans+=dfs(len-,(zero&&i==)?:getnews(i,st),zero&&i==,flag&&i==en);

     }

     if(!flag) dp[len][st][k]=ans;

     return ans;

 }

 LL cal(LL n){

     LL tmp=n;

     int len=;

     while(tmp){

         a[++len]=(int)(tmp%);

         tmp/=;

     }

     return dfs(len,,true,true);

 }

 int main(){

     memset(dp,-,sizeof(dp));

     int T,t=;

     scanf("%d",&T);

     while(++t<=T){

         scanf("%I64d%I64d%d",&aa,&bb,&k);

         printf("Case #%d: %I64d\n",t,cal(bb)-cal(aa-1LL));

     }

     return ;

 }