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

struct bigint {
    int a[N];
    int n = 0;
    bigint(int x = 0) {
        if (x == 0) {
            a[n++] = 0;
        } else {
            while (x) {
                a[n++] = x % 10;
                x /= 10;
            }
        }
    }
    int& operator[] (int i) { return a[i]; }
    void flatten(int len) {
        n = len;
        for (int i = 0; i < n; i++) {
            a[i + 1] += a[i] / 10;  a[i] %= 10;
        }
        while (!a[n]) n--;
    }
};
bigint operator* (bigint& bi, int x) {
    bigint ans;
    int len = bi.n;
    for (int i = 0; i < len; i++) {
        ans[i] = bi[i] * x;
    }
    ans.flatten(len + 11);
    return ans;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, a;
        cin >> n >> a;
        bigint fac(1);
        for (int i = 1; i <= n; i++) {
            fac = fac * i;
        }
        int cnt = 0;
        for (int i = 0; i < fac.n; i++) {
            if (fac[i] == a) cnt++;
        }
        cout << cnt << endl;
    }
    return 0;
}