#include<bits/stdc++.h>

using namespace std;

#define MAXD 1000

const int MAXS = ;

int i,j,k,T,len,d,MASK;

char s[];

long long f[MAXS][MAXD];

long long ans;

long long fac[];

int cnt[];

int main()

{

    fac[] = ;

    for (i = ; i <= ; i++) fac[i] = fac[i-] * i;

    scanf("%d",&T);

    while (T--)

    {

        scanf("%s%d",&s,&d);

        len = strlen(s);

        MASK = ( << len) - ;

        memset(f,,sizeof(f));

        memset(cnt,,sizeof(cnt));

        for (i = ; i < len; i++) cnt[s[i] - '']++;

        f[][] = ;

        for (i = ; i <= MASK; i++)

        {

            for (j = ; j < d; j++)

            {

                for (k = ; k < len; k++)

                {

                    if ((i & ( << k)) == )

                        f[i | ( << k)][(j *  + s[k] - '') % d] += f[i][j];

                }

            }

        }

        ans = f[MASK][];

        for (i = ; i < ; i++) ans /= fac[cnt[i]];

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

    }

    return ;

}