# include<bits/stdc++.h>
using namespace std;
string a1(string m , string n) {
	int b[100000] = {}, v[100000] = {}, c[100000] = {}, x;
	string s;
	s = "";
	for (int q = 0 ; q < m.size() ; q++) {
		b[q] = m[m.size() - q - 1] -'0';
	}
	for (int q = 0 ; q < n.size() ; q++) {
		v[q] = n[n.size() - q - 1] - '0';
	}	
	for (int q = 0 ; q < m.size() ; q++) {
		for (int w = 0 ; w < n.size() ; w++) {
			c[q + w] += v[w] * b[q];
		}
	}
	for (int q = 0 ; q <= m.size() + n.size() ; q++) {
		c[q + 1] += c[q] / 10;
		c[q] %= 10;		
	}
	x = m.size() + n.size();
	while (!c[x]) {
		x--;
	}
	for (int q = x ; q >= 0 ; q--) {
		s += (char)(c[q] + '0');
	}
	return s;
}
int main() {
	int t, x;	
	cin >> t;
	string a[t] = {}, m, c = "0";
	int n[t] = {};
	for (int q = 0 ; q < t ; q++) {
		cin >> n[q] >> a[q];
	} 		
	for (int q = 0 ; q < t ; q++) {
		x = 0;
		for (int w = 1 ; w <= n[q] ; w++) {
			m = "1";
			for (int e = 1 ; e <= w ; e++) {
				int n = e;
				string	b = "";
				while (n > 0) {
					b += (char)(n % 10 + '0');
					n /= 10;
				}
				m = a1(m , b);
			}			
		}
		for (int r = 0 ; r < m.size() ; r++) {
			if (m[r] == a[q][0]) {
				x++;
			}
		}
		cout << x << endl;	
	}	 	
    return 0;
}