#pragma GCC optimize "Ofast"
#include <iostream>
#include <vector>
#include <functional>
#include <array>
#include <cstring>
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) \
	int dp##m[m][m], ndp##m[m][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;\
		for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) dp##m[i][j] = ndp##m[i][j] = 0;\
		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##m[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##m[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;\
		while (l.size()) {\
			int lo = l.back() - '0';\
			int hi = r.back() - '0';\
			l.pop_back();\
			r.pop_back();\
			memset(ndp##m, 0, m*m*sizeof(int));\
			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##m[a][b] += dp##m[j][k];\
						ndp##m[a][b] = fastFix(ndp##m[a][b], mod);\
					}\
					for (int k = m-x; k < m; k++) {\
						int b = k+x-m;\
						ndp##m[a][b] += dp##m[j][k];\
						ndp##m[a][b] = fastFix(ndp##m[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);\
					}\
				}\
			}\
			memcpy(ndp##m, dp##m, m*m*sizeof(int));\
		}\
		cout << fix(out, mod)  << '\n';\
	}\

solveM(0);
solveM(2);
solveM(4);
solveM(6);
solveM(8);
solveM(10);
solveM(12);
solveM(14);
solveM(16);
solveM(18);
solveM(20);
solveM(22);
solveM(24);
solveM(26);
solveM(28);
solveM(30);
solveM(32);
solveM(34);
solveM(36);
solveM(38);
solveM(40);
solveM(42);
solveM(44);
solveM(46);
solveM(48);
solveM(50);
solveM(52);
solveM(54);
solveM(56);
solveM(58);
solveM(60);
solveM(62);
solveM(64);
solveM(66);
solveM(68);
solveM(70);
solveM(72);
solveM(74);
solveM(76);
solveM(78);
solveM(80);
solveM(82);
solveM(84);
solveM(86);
solveM(88);
solveM(90);
solveM(92);
solveM(94);
solveM(96);
solveM(98);
solveM(100);
solveM(102);
solveM(104);
solveM(106);
solveM(108);
solveM(110);
solveM(112);
solveM(114);
solveM(116);
solveM(118);
solveM(120);
function<void(string, string)> solvers[61] = {
	solve0, 
	solve2, 
	solve4, 
	solve6, 
	solve8, 
	solve10, 
	solve12, 
	solve14, 
	solve16, 
	solve18, 
	solve20, 
	solve22, 
	solve24, 
	solve26, 
	solve28, 
	solve30, 
	solve32, 
	solve34, 
	solve36, 
	solve38, 
	solve40, 
	solve42, 
	solve44, 
	solve46, 
	solve48, 
	solve50, 
	solve52, 
	solve54, 
	solve56, 
	solve58, 
	solve60, 
	solve62, 
	solve64, 
	solve66, 
	solve68, 
	solve70, 
	solve72, 
	solve74, 
	solve76, 
	solve78, 
	solve80, 
	solve82, 
	solve84, 
	solve86, 
	solve88, 
	solve90, 
	solve92, 
	solve94, 
	solve96, 
	solve98, 
	solve100, 
	solve102, 
	solve104, 
	solve106, 
	solve108, 
	solve110, 
	solve112, 
	solve114, 
	solve116, 
	solve118, 
	solve120, 
};

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);
	}
}