#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

long long t,l,r,k,ret=,bit[];

struct pnt

{

    long long k[];

}dp[][<<];

void reset()

{

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

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

            for (long long k=;k<=;k++)

                dp[i][j].k[k]=-;

}

void get_bit(long long x)

{

    ret=;

    while (x) {bit[++ret]=x%;x/=;}

}

long long bit_cnt(long long x)

{

    long long ret=;

    while (x) {if (x&) ret++;x>>=;}

    return ret;

}

long long get_sets(long long sets,long long x)

{

    if (sets&(<<x)) return sets;

    sets|=(<<x);

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

    {

        if (sets&(<<i))

        {

            sets^=(<<i);

            return sets;

        }

    }

    return sets;

}

pnt comb(pnt x,pnt y)

{

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

        x.k[i]+=y.k[i];

    return x;

}

pnt dfs(long long pos,long long sets,bool flag)

{

    if (!pos)

    {

        long long now=bit_cnt(sets);pnt ret;

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

        {

            if (i==now) ret.k[i]=;

            else ret.k[i]=;

        }

        return ret;

    }

    if ((!flag) && (~dp[pos][sets].k[])) return dp[pos][sets];

    pnt ans;long long up=flag?bit[pos]:;

    for (long long i=;i<=;i++) ans.k[i]=;

    for (long long i=;i<=up;i++)

        ans=comb(ans,dfs(pos-,get_sets(sets,i),flag&&i==up));

    if (!flag) dp[pos][sets]=ans;

    return ans;

}

long long ask(long long x)

{

    if (!x) return ;

    get_bit(x);long long ans=;

    for (long long i=;i<=ret-;i++)

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

            ans+=dfs(i-,<<j,).k[k];

    for (long long j=;j<=bit[ret]-;j++)

        ans+=dfs(ret-,<<j,).k[k];

    ans+=dfs(ret-,<<bit[ret],).k[k];

    return ans;

}

void work(long long x)

{

    scanf("%lld%lld%lld",&l,&r,&k);

    printf("Case #%lld: %lld\n",x,ask(r)-ask(l-));

}

int main()

{

    scanf("%lld",&t);reset();

    for (long long i=;i<=t;i++) work(i);

    return ;

}