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 int[] num;
{
f = new Flash();
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;
}
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 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);
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);
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
{
while(!st.hasMoreTokens()){
try{
e.printStackTrace();
}
}
return st.nextToken();
}
try{
s = br.readLine().trim();
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
());} }
}