#include<bits/stdc++.h>
using namespace std;
struct bigint{
	int len,s[5050];
	int &operator[](int i){
		return s[i];
	} 
	bigint(int x=0){
		memset(s,0,sizeof(s));
		for(len=1;x;len++){
			s[len]=x%10,x/=10;
		}
		len--;
	}
	void flatten(int L){
		len=L;
		for(int i=1;i<=len;i++){
			s[i+1]+=s[i]/10,s[i]%=10;
		}
		for(;!s[len];)len--;
	}
	void print(){
		for(int i=max(len,1);i>=1;i--){
			cout<<s[i];
		}
		cout<<endl;
	}	
};
bigint operator*(bigint a,int b){
	bigint c;
	int len=a.len;
	for(int i=1;i<=len;i++){
		c[i]=a[i]*b;
	}
	c.flatten(len+11); 
	return c;
}
int main(){
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		int n,a,cnt=0;
		cin>>n>>a;
		bigint ans(1);
		for(int i=1;i<=n;i++){
			ans=ans*i;
		}
		for(int i=1;i<=ans.len;i++){
			if(ans[i]==a)cnt++;
		}
		cout<<cnt<<endl;
	//	ans.print();
	}	
}