#include<bits/stdc++.h>
using namespace std;
//2569 
int t,n,m,a[5000],k=1,s;
int main(){
	cin>>t;
	a[0]=1;
	while(t--){
		cin>>n>>m;
		for(int i=2;i<=n;i++){
			for(int j=0;j<k;j++){
				a[j]=a[j]*i;
			}
			for(int j=0;j<k;j++){
				if(a[j]>=10){
					a[j+1]=a[j+1]+a[j]/10;
					a[j]=a[j]%10;
					k++;
				}
			}
		}
		bool flag=false;
		for(int i=k-1;i>=0;i--){
			if(a[i]!=0)flag=true;
			if(flag){
				if(a[i]==m){
					s++;
				}
			}
		}
		cout<<s<<endl;
		s=0;
		for(int i=0;i<1005;i++){
			a[i]=0;
		}
		a[0]=1;
	}
	return 0;
}