#include <bits/stdc++.h>

using namespace std;

const int mod = (int )(1e9 + 7);

int tmpa[800001], tmpb[800001];
int ww[800001];

int a[18][200001];
int c[800001], f[800001];
int pa[800001], pb[800001];
int pc[800001][3];
int Inv[3][3];

const int magic[3] = {1004535809, 998244353, 104857601};

char str[100001];
int Mod;

int mypow(int x, int y, int p) {
	int sum = 1;
	for (; y; y >>= 1) {
		if (y & 1) sum = 1LL * sum * x % p;
		x = 1LL * x * x % p;
	}
	return sum;
}

struct Unknown {
	int wn[25], P, G;
	void set(int x, int y) {
		P = x, G = y;
		for (int i = 1; i <= 23; i ++)
			wn[i] = mypow(G, (P - 1) / (1 << i), P);
	}
	void change(int* y, int len) {
		for (int i = 1, j = len / 2; i < len - 1; i ++) {
			if (i < j) swap(y[i], y[j]);
			int k = len / 2;
			for (; j >= k; j -= k, k /= 2);
			j += k;
		}
	}
	void NTT(int *y, int len, int on) {
		change(y, len);
		for (int h = 2, id = 1; h <= len; h <<= 1, ++ id) {
			ww[0] = 1;
			for (int i = 1; i < (h >> 1); i ++) ww[i] = 1LL * ww[i - 1] * wn[id] % P;
			for (int j = 0; j < len; j += h)
				for (int k = j; k < j + (h >> 1); k ++) {
					int u = y[k], t = 1LL * y[k + (h >> 1)] * ww[k - j] % P;
					y[k] = (u + t) % P, y[k + (h >> 1)] = (u - t + P) % P;
				}
		}
		if (on == -1) {
			for (int i = 1; i < len / 2; i ++) swap(y[i], y[len - i]);
			int inv = mypow(len, P - 2, P);
			for (int i = 0; i < len; i ++)
				y[i] = 1LL * y[i] * inv % P;
		}
	}
	void mul(int* A, int* B, int len) {
		NTT(A, len, 1);  NTT(B, len, 1);
		for (int i = 0; i < len; i ++)
			A[i] = 1LL * A[i] * B[i] % P;
		NTT(A, len, -1);
	}
};
Unknown ntt[2];

int CRT(int *a)
{
	int x[3];
	for (int i = 0; i < 2; i ++)
	{
		x[i] = a[i];
		for (int j = 0; j < i; j ++)
		{
			int t = (x[i] - x[j] + magic[i]) % magic[i];
			if (t < 0) t += magic[i];
			x[i] = 1LL * t * Inv[j][i] % magic[i];
		}
	}
	int sum = 1, ret = x[0] % Mod;
	for (int i = 1; i < 2; i ++)
	{
		sum = 1LL * sum * magic[i - 1] % Mod;
		ret += 1LL * x[i] * sum % Mod;
		if(ret >= Mod) ret -= Mod;
	}
	return ret;
}

void multiply(int* a, int* b, int len)
{
	for (int i = 0; i < 2; i ++)
	{
		for (int j = 0; j < len; j ++)
			pa[j] = a[j], pb[j] = b[j];
		ntt[i].mul(pa, pb, len);
		for (int j = 0; j < len; j ++)
			pc[j][i] = pa[j];
	}
	for (int i = 0; i < len; i ++) a[i] = CRT(pc[i]);
}

void Prepare()
{
	for (int i = 0; i < 2; i ++) ntt[i].set(magic[i], 3);
	for (int i = 0; i < 2; i ++)
		for (int j = i + 1; j < 2; j ++)
			Inv[i][j] = mypow(magic[i], magic[j] - 2, magic[j]);
}
int dfs(int l, int r, int deep, int cur) {
	if (l > r) {
		a[deep][0 + cur] = 1;
		return 1;
	}
	if (l == r) {
		int sz = 1;
		a[deep][0 + cur] = l;
		a[deep][1 + cur] = 1;
		return 2;
	}
	int mid = (l + r) >> 1;
	int n1 = dfs(l, mid, deep + 1, cur);
	int n2 = dfs(mid + 1, r, deep + 1, cur + n1);
	int len = 1;
	while (len <= 2 * (n2 + 1)) len <<= 1;
	for (int i = 0; i < len; i ++) tmpa[i] = tmpb[i] = 0;
	for (int i = cur; i < cur + n1; i ++) tmpa[i - cur] = a[deep + 1][i];
	for (int i = cur + n1; i < cur + n1 + n2; i ++) tmpb[i - cur - n1] = a[deep + 1][i];
	multiply(tmpa, tmpb, len);
	for (int i = cur; i < cur + n1 + n2 - 1; i ++)
		a[deep][i] = tmpa[i - cur];
	return n1 + n2 - 1;
}

int L;
int get_res() {
	int res = 0;
	for (int i = L - 1; i >= 0; i --)
		res = (res * 10 + c[i]) % Mod;
	return res;
}

void div_op() {
	int res = 0;
	for (int i = L - 1; i >= 0; i --) {
		int tmp = res;
		res = (res * 10 + c[i]) % Mod;
		c[i] = (tmp * 10 + c[i]) / Mod;
	}
	while (L >= 1 && c[L - 1] == 0) -- L;
}

bool zero() {
	return L == 0;
}

int main( ) {
	int T;
	scanf("%d", &T);
	while (T --) { 
		int ans = 1, ans2 = 0;
		Prepare();
		scanf("%s", str);
		int n = (int )(strlen(str));
		for (int i = 0; i < n; i ++) c[i] = str[i] - '0';
		reverse(c, c + n);
		scanf("%d", &Mod);
		L = n;
		int pn = get_res();
		if (pn == Mod - 1) {
			c[0] ++;
			for (int i = 0; i < n; i ++)
				if (c[i] >= 10) c[i + 1] ++, c[i] -= 10;
			if (c[n]) ++ n, ++ L;
		} 
		int r = -1;
		while (!zero()) {
			int tmp = get_res();
			if (r == -1) r = tmp;
			else ans = 1LL * ans * (tmp + 1) % mod;
			div_op();
		}
		if (pn == Mod - 1) printf("%d\n", ans);
		else {
			int N = dfs(1, r, 0, 0);
			for (int i = 0; i < N; i ++)
				if (a[0][i]) ++ ans2;
			printf("%d\n", 1LL * ans * ans2 % mod);
		}
		for (int i = 0; i < n; i ++) c[i] = 0;
		memset(a, 0, sizeof(a));
	}
	return 0;
}