1. #include<bits/stdc++.h>
2. using namespace std;
3. #define FOE(i, s, t) for (int i = s; i <= t; i++)
4. #define FOR(i, s, t) for (int i = s; i < t; i++)
5. #define ff              first
6. #define ss              second
7. #define int             long long
8. #define pb              push_back
9. #define mp              make_pair
10. #define pii             pair<int,int>
11. #define vi              vector<int>
12. #define mii             map<int,int>
13. #define pqb             priority_queue<int>
14. #define pqs             priority_queue<int,vi,greater<int> >
15. #define setbits(x)      __builtin_popcountll(x)
16. #define zrobits(x)      __builtin_ctzll(x)
17. #define mod             1000000007
18. #define inf             1e18
19. #define ps(x,y)         fixed<<setprecision(y)<<x
20. #define mk(arr,n,type)  type *arr=new type[n];
21. #define w(x)            int x; cin>>x; while(x--)
22. #define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
23. mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
24.  
25. int dp[12][92][2][92];
26. vi v;
27. int func(int pos, int sum, int p, int num, int k)
28. {
29.         if (pos >= v.size())
30.         {
31.                 if (sum % k == 0 && num % k == 0)
32.                         return 1;
33.                 return 0;
34.         }
35.         if (dp[pos][sum][p][num] != -1)
36.                 return dp[pos][sum][p][num];
37.         int maxV = 9;
38.         if (p == 0)
39.                 maxV = v[pos];
40.         int res = 0;
41.         FOR(i, 0, maxV + 1)
42.         {
43.                 int temp_p = p;
44.                 if (temp_p==0 && i < v[pos])
45.                         temp_p = 1;
46.                 int temp_num = (10 * num + i) % k;
47.                 int temp_sum = (sum + i) % k;
48.                 res += func(pos + 1, temp_sum, temp_p, temp_num, k);
49.         }
50.         return dp[pos][sum][p][num] = res;
51. }
52. int funcUtil(int a, int k)
53. {
54.         v.clear();
55.         while (a)
56.         {
57.                 v.pb(a % 10);
58.                 a = a / 10;
59.         }
60.  
61.         memset(dp, -1, sizeof(dp));
62.         reverse(v.begin(), v.end());
63.         return func(0, 0, 0, 0, k);
64. }
65. void solve()
66. {
67.         int a, b, k;
68.         cin >> a >> b >> k;
69.         if (k >= 90)
70.         {
71.                 cout << 0 << "\n";
72.                 return ;
73.         }
74.  
75.         cout << funcUtil(b, k) - funcUtil(a - 1, k) << "\n";
76.  
77. }
78. int32_t main()
79. {
80.         FIO;
81. #ifndef ONLINE_JUDGE
82.         freopen("input1.txt", "r", stdin);
83.         freopen("output1.txt", "w", stdout);
84. #endif
85.  
86.         w(tc) {
87.  
88.  
89.                 solve();
90.  
91.         }
92.  
93. }
94.  
95.