#include <stdio.h>
#include <string.h>

#define SIZE 1000

typedef char INT[SIZE];

void mul(INT a, int b, INT c)
{
	memset(c, 0, sizeof(INT));
	for (int i = SIZE - 1; i >= 0; i--)
	{
		int tmp = a[i] * b;
		int j = i;
		while (tmp > 0)
		{
			c[j--] = tmp % 10;
			tmp /= 10;
		}
	}
}

void fac(int n, INT a)
{
	INT b, c;
	memset(b, 0, sizeof(INT));
	b[SIZE - 1] = 1;
	memset(c, 0, sizeof(INT));
	char * t1 = b, * t2 = c, * tmp = NULL;
	while (n)
	{
		mul(t1, n--, t2);
		tmp = t1, t1 = t2, t2 = tmp;		
	}
	memcpy(a, t1, sizeof(INT));
}

int count(INT a, int c)
{
	int ans = 0, i;
	for (i = 0; i < SIZE - 1 && a[i] == 0; i++)
		;
	while (i < SIZE)
	{
		if (a[i++] == c)
			ans++;
	}
	return ans;	
}

int main(void)
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, c;
		scanf("%d%d", &n, &c);
		INT a;
		fac(n, a);
		printf("%d\n",count(a, c));
	}
	return 0;
}