#pragma GCC optimize "Ofast"
#include <iostream>
#include <vector>
#include <functional>
#include <array>
using ll = int;
using namespace std;
using a2 = array<int, 2>;
const ll mod = 1e9+7;

ll sq(ll x) {
	return x*x;
}

ll fastFix(ll x, ll m) {
	if (x >= m) x-=m;
	return x;
}
ll midFix(ll x, ll m){
	return x%m;
}
ll fix(ll x, ll m) {
	return ((x%m)+m)%m;
}

ll modPow(ll n, ll p, ll mod) {
	ll b = n, o = 1;
	while (p) {
		if (p&1) o = (o*b)%mod;
		b = (b*b)%mod;
		p/=2;
	}
	return o;
}
#define solveM(m) \
	void solve##m(string l, string r) {\
		string s = "";\
		while (s.size() + l.size() < r.size()) s += "0";\
		l = s+l;\
		l = "0" + l;\
		r = "0" + r;\
		int om = m;\
		vector<vector<ll>> dp(m, vector<ll>(m));\
		vector<a2> top(l.size()), bot(l.size());\
		vector<ll> topMod(l.size()), botMod(l.size());\
		vector<ll> pref(l.size());\
		for (int i = 1; i < l.size(); i++) {\
			top[i] = top[i-1];\
			bot[i] = bot[i-1];\
			\
			top[i][0] = midFix(top[i][0] + sq(r[i]-'0'), m);\
			top[i][1] = midFix(top[i][1] + r[i]-'0', m);\
			bot[i][0] = midFix(bot[i][0] + sq(l[i]-'0'), m);\
			bot[i][1] = midFix(bot[i][1] + l[i]-'0', m);\
		}\
		for (int i = 1; i < l.size(); i++) {\
			ll suf = 2*modPow(10, l.size()-i-1, m);\
			pref[i] = fix(suf, m);\
			topMod[i] = topMod[i-1]*10 + r[i]-'0';\
			topMod[i] = midFix(topMod[i],m);\
	\
			botMod[i] = botMod[i-1]*10 + l[i]-'0';\
			botMod[i] = midFix(botMod[i],m);\
		}\
		dp[0][0] = 1;\
		ll out = 0;\
	\
		if (fix(top.back()[0] + topMod.back()*2 - sq(top.back()[1]), m) == 0) {\
			out++;\
		}\
		if (l != r && fix(bot.back()[0] + botMod.back()*2 - sq(bot.back()[1]), m) == 0) {\
			out++;\
		}\
	\
		if (l == r) {\
			cout << out << endl;\
			return;\
		}\
	\
		auto test = [&](int x, int d, vector<a2> &prefVals, vector<ll> &prefMod) {\
			ll curSum = midFix(prefVals[x][1] + d, m);\
			ll curSq = midFix(prefVals[x][0] + prefMod[x]*pref[x] + d*pref[x+1] + d*d, m);\
			for (int j = 0; j < m; j++) {\
				int a = midFix(sq(curSum + j), m);\
				int k = fastFix(a-curSq+m, m);\
				out = fastFix((out+dp[j][k]), mod);\
			}\
		};\
		vector<bool> eq(l.size()+1);\
		eq[0] = true;\
		bool eqNow = true;\
		for (int i =0; i < l.size(); i++) {\
			if (l[i] != r[i]) eqNow = false;\
			eq[i+1] = eqNow;\
		}\
		ll base = 1;\
		vector<vector<ll>> ndp(m, vector<ll>(m));\
		while (l.size()) {\
			int lo = l.back() - '0';\
			int hi = r.back() - '0';\
			l.pop_back();\
			r.pop_back();\
			for (int j = 0; j < m; j++) {\
				for (int k = 0; k < m; k++) {\
					ndp[j][k] = 0;\
				}\
			}\
			for (int l = 0; l < 10; l++) {\
				int x = midFix(2*base*l + sq(l), m);\
				for (int j = 0; j < m; j++) {\
					ll a = midFix(j+l, m);\
					for (int k = 0; k+x < m; k++) {\
						ll b = k+x;\
						ndp[a][b] += dp[j][k];\
						ndp[a][b] = fastFix(ndp[a][b], mod);\
					}\
					for (int k = m-x; k < m; k++) {\
						int b = k+x-m;\
						ndp[a][b] += dp[j][k];\
						ndp[a][b] = fastFix(ndp[a][b], mod);\
					}\
				}\
			}\
			base = fix(base*10, m);\
			int x = r.size()-1;\
			for (int i = 0; i < 10; i++) {\
				if (eq[l.size()] && i < hi && i > lo) {\
					test(x, i, top, topMod);\
				}\
				else if (!eq[l.size()]) {\
					if (i < hi) {\
						test(x, i, top, topMod);\
					}\
					if (i > lo) {\
						test(x, i, bot, botMod);\
					}\
				}\
			}\
			swap(dp, ndp);\
		}\
		cout << fix(out, mod)  << '\n';\
	}\

solveM(0);
solveM(1);
solveM(2);
solveM(3);
solveM(4);
solveM(5);
solveM(6);
solveM(7);
solveM(8);
solveM(9);
solveM(10); 
solveM(11); 
solveM(12); 
solveM(13); 
solveM(14); 
solveM(15); 
solveM(16); 
solveM(17); 
solveM(18); 
solveM(19); 
solveM(20); 
solveM(21); 
solveM(22); 
solveM(23); 
solveM(24); 
solveM(25); 
solveM(26); 
solveM(27); 
solveM(28); 
solveM(29); 
solveM(30); 
solveM(31); 
solveM(32); 
solveM(33); 
solveM(34); 
solveM(35); 
solveM(36); 
solveM(37); 
solveM(38); 
solveM(39); 
solveM(40); 
solveM(41); 
solveM(42); 
solveM(43); 
solveM(44); 
solveM(45); 
solveM(46); 
solveM(47); 
solveM(48); 
solveM(49); 
solveM(50); 
solveM(51); 
solveM(52); 
solveM(53); 
solveM(54); 
solveM(55); 
solveM(56); 
solveM(57); 
solveM(58); 
solveM(59); 
solveM(60); 
function<void(string, string)> solvers[61] = {
	solve0, 
	solve1, 
	solve2, 
	solve3, 
	solve4, 
	solve5, 
	solve6, 
	solve7, 
	solve8, 
	solve9, 
	solve10, 
	solve11, 
	solve12, 
	solve13, 
	solve14, 
	solve15, 
	solve16, 
	solve17, 
	solve18, 
	solve19, 
	solve20, 
	solve21, 
	solve22, 
	solve23, 
	solve24, 
	solve25, 
	solve26, 
	solve27, 
	solve28, 
	solve29, 
	solve30, 
	solve31, 
	solve32, 
	solve33, 
	solve34, 
	solve35, 
	solve36, 
	solve37, 
	solve38, 
	solve39, 
	solve40, 
	solve41, 
	solve42, 
	solve43, 
	solve44, 
	solve45, 
	solve46, 
	solve47, 
	solve48, 
	solve49, 
	solve50, 
	solve51, 
	solve52, 
	solve53, 
	solve54, 
	solve55, 
	solve56, 
	solve57, 
	solve58, 
	solve59, 
	solve60, 
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	/*for (int i = 10; i < 100; i++) {
		for (int j = i; j < 100; j++) {
		for (int k = 2; k <= 20; k++) {
		cout << i << ' ' << j << ' ' << k << endl;
		solve(to_string(i), to_string(j), k);
		}
		}
		}*/
	int t; cin >> t;
	while (t--) {
		string l, r; cin >> l >> r;
		int m; cin >> m;

		//int m = fix(rand(), 60)+1;
		//string l = to_string(fix(rand(), 10000));
		//string r = to_string(fix(rand(), 10000) + stoi(l));
		//cout << l <<' ' << r << ' ' << m << endl;
		solvers[m](l, r);
	}
}