#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9+7;
int dp[5001][60][60];
vector<int>pw(5005);
int fix(int x, int m){
	x%=m; x+=m; x%=m;
	return x;
}
int find(int a, int b, int len, int m){
	int ans = 0;
	for(int i = 0; i<m; i++){
		for(int j = 0; j<m; j++){
			int na = a+i-b*j;
			na = fix(na,m);
			if(na==0)ans+=dp[len][i][j];
			ans%=mod;
		}
	}
	
	return ans;
}

int solve(string s, int m){
	int n = s.size();
	if(n==1)return 0;
	int ans = 0;
	dp[0][0][0] = 1;
	pw[0] = 1;
	for(int i = 1; i<=n+2; i++){
		pw[i] = pw[i-1]*10%m;
	}
	for(int i = 1; i<=n; i++){
		for(int a = 0; a<m; a++){ // a encodes x - f(x)
			for(int b = 0; b<m; b++){
				for(int d = 0; d<10; d++){
					int na = a + pw[i-1]*d - b*d; na = fix(na,m);
					int nb = (b+d)%m;
					dp[i][na][nb]+=dp[i-1][a][b];
					dp[i][na][nb]%=mod;
				}
			}
		}
	}
	for(int i = 1; i+1<n; i++){
		for(int d = 1; d<10; d++){
			int a = pw[i]*d%m;
			int b = d;
			ans+=find(a,b,i,m);
			ans%=mod;
		}
	}
	int a = 0; int b = 0;
	for(int i = 0; i<n; i++){
		for(int j = 0; j<=s[i]-'0'; j++){
			if(j==s[i]-'0' && i<n-1)continue;
			if(i==0&&j==0)continue;
			//cout << i << ' ' << j << '\n';
			int na = fix(a + pw[n-i-1]*j - b*j, m);
			int nb = (b+j)%m;
			//cout << na << ' ' << nb << '\n' << '\n';
			ans+=find(na,nb,n-i-1,m);
			//cout << ans << '\n';
			ans%=mod;
		}
		int d = s[i]-'0';
		a = fix(a + pw[n-i-1]*d - b*d, m);
		b = (b+d)%m;
	}
	for(int i = 0; i<=n; i++){
		for(int j = 0; j<m; j++){
			for(int k = 0; k<m; k++){
				dp[i][j][k] = 0;
			}
		}
	}
	return ans;
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while(t--){
		string l,r;
		cin >> l >> r;
		int m;
		cin >> m;
		for(int i = (int)l.size()-1; i>=0; i--){
			if(l[i] == '0'){
				l[i] = '9';
				continue;
			}
			l[i]--;
			break;
		}
		if(l[0] == '0'){
			l.erase(l.begin());
		}
		int v = solve(r,m);
		v-=solve(l,m);
		v%=mod; v+=mod; v%=mod;
		cout << v << '\n';
	}
	return 0;
}