#include<bits/stdc++.h>
using namespace std;
struct bigint
{
    int x[1000],length=0;
    void fuzhi(int n)
    {
    	memset(x,0,sizeof(x));
        length=0;
        while(n)
        {
            x[++length]=n%10;
            n/=10;
        }
    }
    void flatten(int sizee)
    {
        length=sizee;
        for(int i=1;i<=sizee;i++)
        {
            x[i+1]+=x[i]/10;
            x[i]%=10;
        }
       while(x[length]==0)
       {
           length--;
       }
    }
    void write()
    {
        for(int i=length;i>=1;i--) cout<<x[i];
    }
};
bigint operator + (bigint a,bigint b)
{

    bigint c;
    for(int i=1;i<=max(a.length,b.length)+1;i++)
    {
        c.x[i]=a.x[i]+b.x[i];
    }
    c.flatten(max(a.length,b.length)+2);
    return c;
}
bigint operator * (bigint a,int b)
{

    bigint c;
    memset(c.x,0,sizeof(c.x));
    for(int i=1;i<=a.length;i++)
    {
        c.x[i]=a.x[i]*b;
    }
    c.flatten(a.length+5);
    return c;
}
int main()
{
    int T;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int n,m,ans=0;
        cin>>n>>m;
        bigint p;
        p.fuzhi(1);
        for(int i=1;i<=n;i++)
        {
            p=p*i;
        }
        for(int i=1;i<=p.length;i++)
        {
            if(p.x[i]==m)
                ans++;
        }
        cout<<ans<<endl;
    }
}