#include <bits/stdc++.h>
using namespace std;

int a[1005],b[101][2],sum[101];

int main() 
{
	int n,i,j;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<2;j++)
			scanf("%d",&b[i][j]);
	a[0]=1;
	for(int p=0;p<n;p++){
		for(i=2;i<=b[p][0];i++){
			for(j=0;j<100;j++){
				a[j]*=i;
			}
			for(j=0;j<100;j++){
				if(a[j]>9){
					a[j+1]+=a[j]/10;
					a[j]%=10;
				}
			}
		}
		for(i=100;i>=0&&a[i]==0;i--);
		for(j=i;j>=0;j--){
			if(a[j]==b[p][1])sum[p]++;
		}
		printf("%d ",sum[p]);
}
	return 0;
}