#include<stdio.h>
int multiply(int s[],int i,int &len){
	for(int j=0;j<len;j++){
		s[j]*=i;
	}
	len+=2;
	for(int j=0;j<len;j++){
		s[j+1]+=s[j]/10;
		s[j]%=10;
	}
	while(!s[len-1]) len--;
}
int main(){
	int num;
	scanf("%d",&num); 
	while(num){
		int s[100000]{};
		s[0]=1;
		int n,len=1;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			multiply(s,i,len);
		}
		int ser;
		long long int a=0;
		scanf("%d",&ser);
		for(int i=len-1;i>=0;i--){
			if(s[i]==ser) a++;
		}
		printf("%ld\n",a);
		num--;
	}
}