#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (ll i=j;i<=k;++i)

#define ll long long

ll T,n,d,dp[1<<10][1001],a[11],l,_pow[12],fac[12],cnt[12];

char s[11];

ll cot(ll x)

{

    ll ret=0;

    while (x)ret+=(1&x),x>>=1;

    return ret;

}

int main()

{

    scanf("%lld",&T);

    _pow[0]=1;F(i,1,10) _pow[i]=_pow[i-1]*10;

    fac[0]=1;F(i,1,10) fac[i]=fac[i-1]*i;

    while (T--)

    {

        memset(cnt,0,sizeof cnt);

        scanf("%s",s);scanf("%lld",&d);l=strlen(s);

        F(i,0,l-1) a[i]=s[i]-'0',++cnt[a[i]];

        memset(dp,0,sizeof dp);

        dp[0][0]=1;

        F(i,0,(1<<l)-1)

        {

            ll tmp=cot(i);

            F(j,0,d-1) F(k,0,l-1)

                if (!(i&(1<<k)))

                    dp[i|(1<<k)][(j+_pow[tmp]*a[k])%d]+=dp[i][j];

        }

        ll ans=dp[(1<<l)-1][0];

        F(i,0,9) ans/=fac[cnt[i]];

        printf("%lld\n",ans);

    }

}