#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int i,B[1005],n,m,sum = 0;
	    scanf("%d%d", &n, &m);
	    memset(B,0,sizeof(B));
	    B[0]=1;
	    for(int i = 2;i <= n; i++){
	        for(int j = 0; j < 1005; j++)
	            B[j]*=i;
	        for(int j = 0; j < 1005; j++)
	            if (B[j] > 9){
	                B[j+1] += B[j]/10;
	                B[j] %= 10;
	            }
	    }
	    for(i = 1005; i>=0 && B[i]==0; i--);
	    for(int j = i; j >= 0; j--){
	    	if(B[j] == m)
				sum++;	
		}
		printf("%d\n", sum);
	}
	return 0; 
}