/*
    created by: nitin23329
    on Date: 09/06/21
*/

import java.io.*;
import java.util.*;
/*****************************************WRITING CODE STARTS HERE******************************************/
 class CodeForces {
    static int[][][][] dp =  new int[11][100][100][2];
    private static int memo(int i,int sum,int currRem,int isBounded,int k,int[] digitArray){
        if(digitArray.length == i) {
            return sum == 0 && currRem  ==0 ? 1 :0;
        }
        if(dp[i][sum][currRem][isBounded]!=-1)return dp[i][sum][currRem][isBounded];
        int ans = 0;
        if(isBounded==1){
            for(int digit = 0 ; digit <= digitArray[i];digit++){
                int currPlace = (int)((digit * power(10,digitArray.length -i-1))%k);
                ans += memo(i+1,(sum + digit)%k,(currRem + currPlace)%k,digit == digitArray[i]?1:0,k,digitArray);
            }
        }else {
            for(int digit = 0 ; digit <= 9;digit++) {
                int currPlace = (int) ((digit * power(10, digitArray.length - i - 1)) % k);
                ans += memo(i + 1, (sum + digit) % k, (currRem + currPlace) % k, 0, k, digitArray);
            }
        }
        return dp[i][sum][currRem][isBounded] = ans;
    }
    private static int helper(int n,int k){
        int digitLength = countDigitBase10(n);
        int[] digitArray = new int[digitLength];
        int nn = n;
        for(int i = digitLength-1;i>=0;i--){
            digitArray[i] = nn % 10;
            nn/=10;
        }
        // currSum can be digitLength * 9
        // currRem can be upto range 0 to k

        for(int i=0;i<digitLength;i++)
            for(int j=0;j<dp[0].length;j++)
                for(int kk=0;kk<k;kk++)
                    Arrays.fill(dp[i][j][kk],-1);

        return memo(0,0,0,1,k,digitArray);
    }
    private static void solve() {
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();
        if(k>=100){
            out.println(0);
            return;
        }
        out.println(helper(b,k) - (a>1?helper(a-1,k):1));

    }

    /*****************************************WRITING CODE ENDS HERE******************************************/

    public static void main(String[] args){
        FIO(false);
        int testCase = 1;
        testCase = sc.nextInt();
        int start = 0;
//        while (testCase-- > 0) solve();
        while (start++<testCase){
            out.print("Case "+start+": ");
            solve();
        }
        closeIO();
    }

    static Scanner sc ;                     // FAST INPUT
    static PrintWriter out;                // FAST OUTPUT
    static PrintWriter debug ;             // DEBUG IN FILE : debug.txt


    /**************************************HELPER FUNCTION STARTS HERE ************************************/

    public static int mod = (int) 1e9 + 7;
    public static final int INT_MAX = Integer.MAX_VALUE;
    public static final int INT_MIN = Integer.MIN_VALUE;
    public static final long LONG_MAX = Long.MAX_VALUE;
    public static final long LONG_MIN = Long.MIN_VALUE;
    public static final double DOUBLE_MAX = Double.MAX_VALUE;
    public static final double DOUBLE_MIN = Double.MIN_VALUE;
    public static final String YES = "YES";
    public static final String NO = "NO";

    public static void sort(int[] a, boolean isAscending) {
        ArrayList<Integer> temp = new ArrayList<>();
        for (int j : a) temp.add(j);
        sort(temp, isAscending);
        for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
    }

    public static void sort(long[] a, boolean isAscending) {
        ArrayList<Long> temp = new ArrayList<>();
        for (long ele : a) temp.add(ele);
        sort(temp, isAscending);
        for (int i = 0; i < a.length; i++) a[i] = temp.get(i);
    }

    public static void sort(List list, boolean isAscending) {
        if (isAscending)
            Collections.sort(list);
        else Collections.sort(list, Collections.reverseOrder());
    }
    // count the length of a number, time O(1)
    public static int countDigitBase10(long n){
        return (int)(1 + Math.log10(n));
    }

    // euclidean algorithm
    public static long gcd(long a, long b) {
        // time O(max (loga ,logb))
        long x = Math.min(a, b);
        long y = Math.max(a, b);
        if (y % x == 0) return x;
        return gcd(y % x, x);
    }

    public static long lcm(long a, long b) {
        // lcm(a,b) * gcd(a,b) = a * b
        return (a / gcd(a, b)) * b;
    }

    public static long power(long x, long n) {
        // time O(logn)
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans *= x;
                ans %= mod;
                n--;
            } else {
                x *= x;
                x %= mod;
                n >>= 1;
            }
        }
        return ans;
    }

    public static long factorial(long n) {
        long fact = 1L;
        for (int i = 2; i <= n; i++) fact = (fact * i) % mod;
        return fact;
    }

    public static long firstDivisor(long n) {
        if (n == 1 || n == 0) return n;
        for (long i = 2; i * i <= n; i++)
            if (n % i == 0) return i;
        return -1;
    }

    public static int ncr(int n, int r) {
        // time O(n+r)
        if (r > n)
            return 0;
        long[] inv = new long[r + 1];
        inv[1] = 1;
        // Getting the modular inversion
        // for all the numbers
        // from 2 to r with respect to m
        for (int i = 2; i <= r; i++) {
            inv[i] = mod - (mod / i) * inv[mod % i] % mod;
        }
        int ans = 1;
        // for 1/(r!) part
        for (int i = 2; i <= r; i++) {
            ans = (int) (((ans % mod) * (inv[i] % mod)) % mod);
        }
        // for (n)*(n-1)*(n-2)*...*(n-r+1) part
        for (int i = n; i >= (n - r + 1); i--) {
            ans = (int) (((ans % mod) * (i % mod)) % mod);
        }
        return ans;
    }

    public static long max3(long a, long b, long c) { return max2(max2(a, b), c);}

    public static long max2(long a, long b) {return Math.max(a, b);}

    public static long min3(long a, long b, long c) {return min2(min2(a, b), c);}

    public static long min2(long a, long b) { return Math.min(a, b); }

    public static int max3(int a, int b, int c) { return max2(max2(a, b), c); }

    public static int max2(int a, int b) { return Math.max(a, b); }

    public static int min3(int a, int b, int c) { return min2(min2(a, b), c); }

    public static int min2(int a, int b) {
        return Math.min(a, b);
    }

    /**************************************HELPER FUNCTION ENDS HERE ************************************/

    /*****************************************FAST INPUT STARTS HERE *************************************/

    public static void FIO(boolean isDebug){
        sc = new Scanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        if(isDebug){
            try {
                debug = new PrintWriter(new FileOutputStream("debug.txt"));
            }catch (IOException e){
                e.printStackTrace();
            }
        }

    }
    public static void closeIO(){
        sc.close();
        out.flush();
        out.close();
        if(debug!=null){
            debug.flush();
            debug.close();
        }
    }

    private static class Scanner {
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer st = new StringTokenizer("");

        public String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();

        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public int[] set_int_array(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = nextInt();
            return arr;
        }

        public long[] set_long_array(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) arr[i] = nextLong();
            return arr;
        }
        public double[] set_double_array(int n){
            double[] arr = new double[n];
            for(int i =0;i<n;i++)arr[i] = sc.nextDouble();
            return arr;
        }

        public int[][] set_2D_int_array(int n) {
            return set2DIntArray(n, n);
        }

        public int[][] set2DIntArray(int row, int col) {
            int[][] arr = new int[row][col];
            for (int i = 0; i < row; i++)
                for (int j = 0; j < col; j++)
                    arr[i][j] = nextInt();
            return arr;
        }

        public long[][] set_2D_long_array(int n) {
            return set2DlongArray(n, n);
        }

        public long[][] set2DlongArray(int row, int col) {
            long[][] arr = new long[row][col];
            for (int i = 0; i < row; i++)
                for (int j = 0; j < col; j++)
                    arr[i][j] = nextLong();
            return arr;
        }

        public char[][] set_2D_char_array(int n) {
            return set2DCharArray(n, n);
        }

        public char[][] set2DCharArray(int row, int col) {
            char[][] ch = new char[row][col];
            for (int i = 0; i < row; i++)
                ch[i] = sc.next().toCharArray();
            return ch;
        }

        public void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
    /*****************************************FAST INPUT ENDS HERE *************************************/
}