#include<bits/stdc++.h>
#define N 100000

using namespace std;

int a[N];

int t, n, m;

int q()
{
	int i, j;
	int len = 1, cnt = 0;
	
	memset(a, 0, sizeof(a));
	a[1] = 1;
	for(i = 2; i <= n; i++)
	{
		for(j = 1; j <= len; j++)
		{
			a[j] = a[j] * i;
		}
		for(j = 1; j <= len + 15; j++)
		{
			a[j + 1] += a[j] / 10;
			a[j] = a[j] % 10;
		}
		while(a[len + 1] != 0)
		{
			len++; 
		}
	}
	for(i = 1; i <= len; i++)
	{
		if(a[i] == m)
		{
			cnt++;
		}
	}
	return cnt;
}

int main()
{
	int i;
	ios::sync_with_stdio(0);
	
	cin >> t;
	for(i = 1; i <= t; i++)
	{
		cin >> n >> m;
		cout << q() << endl;
	}
	return 0;
}