#include<iostream>
using namespace std;
long long b[5005],n,x,ans;
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>x;//输入 
		b[0]=1;//初始化 
		for(int i=2;i<=n;i++){//阶乘的话1方是1么，所以直接从2开始 
			for(int j=0;j<5000;j++){
				b[j]*=i;//把每一位都乘i 
			}
			for(int j=0;j<5000;j++){
				if(b[j]>=10){//判断有没有到进位标准 
					b[j+1]+=b[j]/10;//进位 
					b[j]%=10;//取余 
				}
			} 
		}
		int cnt;//记录位置 
		for(int i=5000;i>=1&&b[i]==0;i--)cnt=i;//不断寻找 
		for(int i=cnt-1;i>=1;i--){//利用位zhi 
			if(b[i]==x) ans++;
		}
		cout<<ans<<endl;
	} 
}