import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.io.*;
import java.util.*;

public class Main
{
    static int a, b, k;
    static int[] arr;
    static char[] s;
    static Integer[][][][] dp;
    static int[] num;
    public static void main(String[] args) throws IOException
    {
        f = new Flash();
        out = new PrintWriter(System.out);
        
        int T = ni();
        for(int tc = 1; tc <= T; tc++){
            a = ni(); b = ni(); k = ni(); 
            sop("Case " + tc + ": " + fn());
        }
        
        out.flush(); out.close();
    }
    
    static int fn()
    {
        return solve(b) - solve(a-1);
    }
    
    static int solve(int n){
        int LEN = len(n);
        num = new int[LEN];
        int x = LEN-1;
        while(n > 0){
            int d = n%10;
            num[x--] = d;
            n /= 10;
        }
        
        dp = new Integer[LEN][k][2][k];
        return recurse(0, 0, 0, 0, LEN-1);
    }
    
    // 6452
    // (6*10^3) + (4*10^2) + (5*10^1) + (2*10^0);
    // 6000 + 400 + 50 + 2 = 6452
    // (x1 + x2) % p == (x1%p + x2%p) % p
    static int recurse(int pos, int rem, int f, int rem2, int p){
        if(pos == num.length){
            if(rem == 0 && rem2 == 0) return 1;
            return 0;
        }    
        
        if(dp[pos][rem][f][rem2] != null) return dp[pos][rem][f][rem2];
        int max;
        if(f == 0) max = num[pos];
        else max = 9;
        
        int tens = 1;
        for(int i = 1; i <= p; i++){
            tens *= 10;
            tens %= k;
        }
        
        int ans = 0;
        for(int d = 0; d <= max; d++){
            int nrem = rem;
            nrem += d; nrem %= k;
            
            int nrem2 = rem2;
            nrem2 += d*tens; nrem2 %= k;
            
            int nf = f;
            if(f == 0 && d < num[pos]) nf = 1;
            
            ans += recurse(pos+1, nrem, nf, nrem2, p-1);
        }
        
        return dp[pos][rem][f][rem2] = ans;
    }
    
    static int len(int n){
        int ret = 0;
        while(n > 0){
            n /= 10;
            ret++;
        }
        
        return ret;
    }
    
    static Flash f;
    static PrintWriter out;
    static final long mod = (long)1e9+7;
    static final long inf = Long.MAX_VALUE;
    static final int _inf = Integer.MAX_VALUE;
    static final int maxN = (int)5e5+5;
    static long[] fact, inv;
    
    static void sort(int[] a){
        List<Integer> A = new ArrayList<>();
        for(int i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static void sort(long[] a){
        List<Long> A = new ArrayList<>();
        for(long i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static void print(int[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static void print(long[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static int swap(int itself, int dummy){return itself;}
    static long swap(long itself, long dummy){return itself;}
    static void sop(Object o){out.println(o);}
    static int ni(){return f.ni();}
    static long nl(){return f.nl();}
    static double nd(){return f.nd();}
    static String next(){return f.next();}
    static String ns(){return f.ns();}
    static char[] nc(){return f.nc();}
    static int[] arr(int len){return f.arr(len);}
    static int gcd(int a, int b){if(b == 0) return a; return gcd(b, a%b);}
    static long gcd(long a, long b){if(b == 0) return a; return gcd(b, a%b);}
    static int lcm(int a, int b){return (a*b)/gcd(a, b);}
    static long lcm(long a, long b){return (a*b)/gcd(a, b);}
    
    static class Flash
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next(){
            while(!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            
            return st.nextToken();
        }
        
        String ns(){
            String s = new String();
            try{
                s = br.readLine().trim();
            }catch(IOException e){
                e.printStackTrace();
            }
            
            return s;
        }
        
        int[] arr(int n){
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = ni();
            return a;
        }
        
        char[] nc(){return ns().toCharArray();}
        int ni(){return Integer.parseInt(next());}
        long nl(){return Long.parseLong(next());}
        double nd(){return Double.parseDouble(next());}
    }
}