#include <stdio.h>
#include <string.h>

void power(int num1,int answer[])
{
	int i,j,q,p=1;
	for(i=2;i<=num1;i++){
		for(j=0;j<p;j++){
			answer[j]*=i;
		}
		for(j=0;j<p;j++){
			q=answer[j]/10;
			answer[j]%=10;;
			while(q>0){
				answer[j+1]+=q%10;
				q/=10;
				if(j+1>=p){
					p++;
				}
			}
		}
	}
}
int main()
{
	int n,a,b,i,j,k,cnt=0,len;
	int result[10000]={1};
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d",&a,&b);
		power(a,result);
		len=10000-1;
		while(result[len]==0){
			len--;
		}
		for(j=0;j<len;j++){
			if(result[j]==b){
				cnt++;
			}
		}
		printf("%d\n",cnt);
		for(k=0;k<10000;k++){
			result[k]=0;
		}
		result[0]=1;
		cnt=0;
	}
	
    return 0;
}