#include <bits/stdc++.h>
 
using namespace std;
 
const int MaxN = (int)1e4 + 10;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

const long long MOD2 = 8LL * MOD * MOD;

bool goodMask[1 << 10];
int p, q;

struct Node {
	int dp[16][1 << 10];
	Node() {
		memset(dp, 0, sizeof(dp));
	}
} ONE;

void add(int &a, int b) {
	if ((a += b) >= MOD) {
		a -= MOD;
	}
}

int rev(int x) {
	return x == 1 ? 1 : 1LL * (MOD - MOD / x) * rev(MOD % x) % MOD;
}

void fwht(int P[], int n, bool inverse) {
    for (int len = 1; 2 * len <= n; len <<= 1) {
        for (int i = 0; i < n; i += 2 * len) {
            for (int j = 0; j < len; ++j) {
                int u = P[i + j];
                int v = P[i + len + j];
                P[i + j] = u + v;
                if (P[i + j] >= MOD) {
					P[i + j] -= MOD;
				}
                P[i + len + j] = u - v;
                if (P[i + len + j] < 0) {
					P[i + len + j] += MOD;
				}
            }
        }
    }
    
    if (inverse) {
		int x = rev(n);
        for (int i = 0; i < n; ++i) {
            P[i] = 1LL * P[i] * x % MOD;
		}
    }
}

int chk[16][1 << 10];
long long chk2[16][1 << 10];

void add(Node &res, const Node &a, const Node &b) {
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 1 << 10; ++j) {
			chk[i][j] = 0;
		}
	}
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 1 << 10; ++j) {
			chk[i][j] = a.dp[i][j];
			add(chk[i][j], b.dp[i][j]);
		}
	}
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 1 << 10; ++j) {
			res.dp[i][j] = chk[i][j];
		}
	}
}

int x[16][1 << 10], y[16][1 << 10], z[16][1 << 10];

void mul(Node &res, const Node &a, const Node &b) {	
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 1 << 10; ++j) {
			x[i][j] = a.dp[i][j];
			y[i][j] = b.dp[i][j];
			z[i][j] = 0;
		}
		fwht(x[i], 1 << 10, false);
		fwht(y[i], 1 << 10, false);
	}
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < p; ++j) {
			int f = (i + j) % p;
			for (int k = 0; k < 1 << 10; ++k) {
				z[f][k] = (z[f][k] + 1LL * x[i][k] * y[j][k]) % MOD;
			}
		}
	}
	for (int j = 0; j < p; ++j) {
		fwht(z[j], 1 << 10, true);
		for (int i = 0; i < 1 << 10; ++i) {
			res.dp[j][i] = z[j][i];
		}
	}
}

int mPow(int a, int n, int mod = MOD) {
	int r = 1;
	while (n > 0) {
		if (n & 1) {
			r = 1LL * r * a % mod;
		}
		a = 1LL * a * a % mod;
		n >>= 1;
	}
	return r;
}

vector < int > getBinary(long long x) {
	vector < int > res;
	while (x > 0) {
		res.push_back(x & 1);
		x /= 2;
	}
	res.pop_back();
	reverse(res.begin(), res.end());
	return res;
}

Node GP(Node a, long long k) {
	if (k == 0) {
		return ONE;
	}
	vector < int > bits = getBinary(k);
	Node res = a, tmp = a, temp;
	for (auto &x : bits) {
		mul(temp, res, tmp);
		add(res, temp, res);
		mul(tmp, tmp, tmp);
		if (x & 1) {
			mul(tmp, tmp, a);
			add(res, res, tmp);
		}
	}
	add(res, res, ONE);
	return res;
}

bool good(int x) {
	int mask = 0;
	while (x > 0) {
		mask ^= 1 << (x % 10);
		x /= 10;
	}
	return goodMask[mask];
}

int dp[50][16][1 << 10];

int stupid(int s, long long k) {
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;
	int ans = 0;
	for (int len = 0; len < k; ++len) {
		for (int ost = 0; ost < s; ++ost) {
			for (int mask = 0; mask < 1 << 10; ++mask) {
				for (int digit = 0; digit < 10; ++digit) {
					int nost = (digit * mPow(10, len, s) + ost) % s;
					int nmask = mask ^ (1 << digit);
					add(dp[len + 1][nost][nmask], dp[len][ost][mask]);
					if (nost == 0 && digit > 0 && goodMask[nmask]) {
						add(ans, dp[len][ost][mask]);
					}
				}
			}
		}
	}
	return ans + 1;
}

int a[6][1 << 10][16 + 1][16], b[6][1 << 10][16 + 1][16];
int inv[22][22];

int solve(int s, long long k) {
	p = s, q = 1;
	while (p % 2 == 0) {
		p /= 2;
		q *= 2;
	}
	while (p % 5 == 0) {
		p /= 5;
		q *= 5;
	}
	int res = 1;
	int step = mPow(10, min(k, 4LL));
	for (int i = s; i < step; i += s) {
		res += good(i);
	}
	if (k <= 4) {
		return res;
	}
	k -= 4;
	Node block;
	for (int i = 0; i < p; ++i) {
		for (int j = 0; j < 1 << 10; ++j) {
			block.dp[i][j] = a[5][j][p][i];
		}
	}
	Node x = GP(block, (k - 1) / 6), y, z, w;
	if (k > 6) {
		y = GP(block, (k - 7) / 6);
	}
	for (int ost = 1; ost <= 6; ++ost) {
		if (k < ost) {
			continue;
		}
		for (int i = 0; i < p; ++i) {
			for (int j = 0; j < 1 << 10; ++j) {
				z.dp[i][j] = b[ost - 1][j][p][i];
			}
		}
		mul(w, z, (k - ost) / 6 == (k - 1) / 6 ? x : y);
		for (int i = 0; i < s; i += q) {
			int who = 0;
			if (p > 1) {
				who = (p - i % p) * inv[p][10000 % p] % p;
			}
			for (int j = 0; j < 1 << 10; ++j) {
				add(res, 1LL * w.dp[who][j] * a[3][j][s][i] % MOD);
				for (int l = 0; l < 10; ++l) {
					add(res, 1LL * w.dp[who][j ^ (1 << l)] * a[3][j][s][i] % MOD);
				}
			}
		}
	}
	return res;
}

int main() {
//	freopen("input.txt", "r", stdin);
	memset(inv, -1, sizeof(inv));
	for (int x = 1; x <= 16; ++x) {
		for (int y = 1; y < x; ++y) {
			for (int z = 1; z < x; ++z) {
				if ((y * z) % x == 1) {
					inv[x][y] = z;
				}
			}
		}
	}
    for (int ten = 1, step = 10; ten <= 6; ++ten, step *= 10) {
        for (int i = 0; i < step; ++i) {
            int x = i, mask = 0, it = ten;
            while (it --> 0) {
				 mask ^= 1 << (x % 10);
				 x /= 10;
			 }
            for (int s = 1; s <= 16; ++s) {
                a[ten - 1][mask][s][i % s]++;
                if (i >= step / 10) {
					b[ten - 1][mask][s][i % s]++;
				}
            }
        }
    }
	for (int i = 0; i < 10; ++i) {
		goodMask[1 << i] = 1;
	}
	goodMask[0] = 1;
	ONE.dp[0][0] = 1;
	int t;
	scanf("%d", &t);
	assert (1 <= t && t <= 20);
	while (t --> 0) {
		int s;
		long long k;
		scanf("%d%lld", &s, &k);
		assert (1 <= s && s <= 16);
		assert (1 <= k && k <= 1e18);
		printf("%d\n", solve(s, k));
//		printf("%d\n", stupid(s, k));
	}
/*	for (int s = 1; s <= 16; ++s) {
		for (int k = 1; k <= 30; ++k) {
			cout << s << ' ' << k << '\n';
			assert (solve(s, k) == stupid(s, k));
		}
	}*/
	return 0;
}