#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, T, H, W, L, R;
int N, M, K, T, H, W, L, R;

constexpr int SMALL = 10000;

int by[10000][10];
int ten[9];

long long func(int a, int b) {
	if (a < b)return 0;
	long long mx = a / b;
	mx--;
	long long ret = 0;
	{
		int add = b % SMALL;
		int c = 0;
		for (int i = 0; i < SMALL; i++) {
			c += add;
			if (c >= SMALL) {
				c -= SMALL;
			}
			if (i <= mx % SMALL) {
				ret += (1 + mx / SMALL) * by[c][N];
			}
			else {
				ret += (0 + mx / SMALL) * by[c][N];
			}
		}
	}
	{
		ret += min(a, ((N + 1) * (ten[8]) - 1)) / b;
		ret -= min(a, ((N + 0) * (ten[8]) - 1)) / b;
		for (int i = 0; i < 10; i++) {
			ret += min(a, (i * ten[8] + (N + 1) * (ten[7]) - 1)) / b;
			ret -= min(a, (i * ten[8] + (N + 0) * (ten[7]) - 1)) / b;
		}
		for (int i = 0; i < 100; i++) {
			ret += min(a, (i * ten[7] + (N + 1) * (ten[6]) - 1)) / b;
			ret -= min(a, (i * ten[7] + (N + 0) * (ten[6]) - 1)) / b;
		}
		for (int i = 0; i < 1000; i++) {
			ret += min(a, (i * ten[6] + (N + 1) * (ten[5]) - 1)) / b;
			ret -= min(a, (i * ten[6] + (N + 0) * (ten[5]) - 1)) / b;
		}
		for (int i = 0; i < 10000; i++) {
			ret += min(a, (i * ten[5] + (N + 1) * (ten[4]) - 1)) / b;
			ret -= min(a, (i * ten[5] + (N + 0) * (ten[4]) - 1)) / b;
		}
	}
	return ret;
}

void Solve() {
	cin >> L >> R >> K >> N;
	cout << func(R, K) - func(L - 1, K) << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < 10000; i++) {
		for (int j = 1; j < 10; j++) {
			int box = i;
			while (box) {
				by[i][j] += box % 10 == j;
				box /= 10;
			}
		}
	}
	ten[0] = 1;
	for (int i = 1; i < 9; i++) {
		ten[i] = ten[i - 1] * 10;
	}
	cin >> T;
	while (T--) {
		Solve();
	}
}