#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int A[5001];

//int len = 1; //阶乘n的位数
//1.高精度*低精度
void mul(int &len, int k)
{
    int g = 0, i; //进位
    for (i = 0; i < len; i++)
    {
        A[i] = A[i] *k + g;
        g = A[i] / 10; //进位
        A[i] = A[i] % 10; //保留个位数
        //if (A[len])
        //    len++;
    }
    //处理最高位溢出:
    while(g > 0) //还有进位,进位不为0
    {
        A[i] = g / 10;
        g %= 10;
        i++;
    }
    len = i - 1;
    
}
//打印函数:
void  printInt(int &len, int x)
{
    int num = 0;
    for (int i = len - 1; i >= 0; i--)
    {
     if (A[i] == x)
        num++; 
    }
    
    cout << num << endl;
}

int main(void)
{
    
    int t;
    cin >> t;//t行数据
    
    while(t--) //查询次数
    {
        int len = 1;
        //数组初始化为0:
        for (int i = 0; i <= 5000; i++)
            A[i] = 0;
        A[0] = 1; //1! = 0;
       
        int n = 0, a = 0;
        cin >> n >> a;//n的阶乘 求a出现的次数
        
        for (int i = 2; i <= n; i++)
         mul(len, i);
    
        printInt(len, a);
        
    }
        
    return 0;
}