#include <stdio.h>

const int dig[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int solve_DP(int R, int K, int C)
{
	static int dp[2][1001], r[10];
	int d, i, j, k, RR, cur, prev, ans = 0;
	for (d = 0, RR = R; RR > 0; d++, RR /= 10) r[d] = RR % 10;
	for (k = 0; k < K; k++) {
		dp[0][k] = 0;
		dp[1][k] = 0;
	}
	for (d--, cur = 1, prev = 0; d >= 0; d--, cur ^= 1, prev ^= 1) {
		for (k = 0; k < K; k++) dp[cur][k] = 0;
		for (k = 0; k < K; k++) {
			if (dp[prev][k] == 0) continue;
			for (i = 0, j = k * 10 % K; i <= 9; i++, j++) {
				if (j == K) j = 0;
				dp[cur][j] += dp[prev][k];
				if (i == C) {
					if (j * dig[d] % K != 0) ans += dp[prev][k] * ((dig[d] - 1 + j * dig[d] % K) / K);
					else ans += dp[prev][k] * ((dig[d] - 1 + K) / K);
				}
			}
			dp[prev][k] = 0;
		}
		for (i = 0, j = RR * 10 % K; i < r[d]; i++, j++) {
			if (j == K) j = 0;
			dp[cur][j]++;
			if (i == C) {
				if (j * dig[d] % K != 0) ans += (dig[d] - 1 + j * dig[d] % K) / K;
				else ans += (dig[d] - 1 + K) / K;
			}
		}
		if (j == K) j = 0;
		RR = j;
		if (r[d] == C) {
			if (j * dig[d] % K != 0) ans += (R % dig[d] + j * dig[d] % K) / K;
			else ans += (R % dig[d] + K) / K;
		}
	}
	return ans;
}

int main()
{
	int T, L, R, K, C;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &L, &R, &K, &C);
		if (K <= 700) printf("%d\n", solve_DP(R, K, C) - solve_DP(L - 1, K, C)); // 750 -> TLE
	}
	fflush(stdout);
	return 0;
}