#include <bits/stdc++.h>
using namespace std;
struct bigint{
	int d[4000];
	int len;
	bigint(){
		memset(d,0,sizeof(d));
		len = 0;
	}
};
int n;
bigint mulit(bigint a,int b){
	bigint c;
	int carry = 0;
	for(int i = 0;i<a.len;++i){
		int t = a.d[i] * b + carry;
		c.d[c.len++] = t%10;
		carry = t/10;
	}
	while(carry){
		c.d[c.len++] = carry;
		carry = 0;
	}
	return c;
}
int main(){
	cin>>n;
	int x,y;
	while(n--){
		cin>>x>>y;
		bigint b1;
		b1.len=1,b1.d[0]=1;
		for(int i = 2;i<=x;++i){
			b1 = mulit(b1,i);
		}
		int ans = 0;
		for(int i = 0;i<b1.len;++i){
			if(b1.d[i]==y){
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}