#include<stdio.h>
int a,b,len=1,c1[100000],c[100000];
int main(){
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		scanf("%d%d",&a,&b);
		for(int j=2;j<=len;j++) c[j]=0;
		c[1]=1;
		len=1;
		for(int j=1;j<=a;j++){
			for(int k=1;k<=len;k++){
				c[k]=j*c[k];
			}
			for(int k=1;k<=len;k++){
				c[k+1]+=c[k]/10;
				c[k]=c[k]%10;
			}
			if(c[len+1]!=0) len++;
		}
		//printf("%d ",len);
		for(int j=1;j<=len;j++){
				//printf("%d ",c[j]);
				if(c[j]==b) c1[i]++;
		}
		//if(a==0&&b!=0) c1[i]=0;
	}
	for(int i=1;i<=t;i++) printf("%d\n",c1[i]);
	return 0;
}