#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int bit[];

ll dp[][][][][][];

bool mycheck(int p[], int k, int newin) {

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

        if(p[i] == newin) return false;

    return true;

}

ll dfs(int now, int p[], int k, bool flag) {

    if(now <= -) return ;

    if(!flag && dp[now][p[]][p[]][p[]][p[]][k] != -)

        return dp[now][p[]][p[]][p[]][p[]][k];

    int step = flag ? bit[now] : ;

    ll ret = ;

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

        if(mycheck(p, k, i)){

            int newp[];

            if(i ==  && p[] == ){

                newp[] = newp[] = newp[] = newp[] = ;

            }else{

                newp[] = p[];newp[] = p[];

                newp[] = p[];newp[] = i;

            }

            ret += dfs(now - , newp, k, flag && (i == step));

        }

    }

    if(!flag) dp[now][p[]][p[]][p[]][p[]][k] = ret;

    return ret;

}

ll solve(ll n, int k){

    if(n == ) return ;

    int cnt = ;

    while(n){

        bit[cnt ++] = n % ;

        n /= ;

    }

    int p[] = {, , , };

    return dfs(cnt - , p, k, true);

}

int main(){

    ll l, r; int k;

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

    while(~scanf("%lld%lld%d", &l, &r, &k)){

        printf("%lld\n", solve(r, k) - solve(l - , k));

    }

    return ;

}