#include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<string>

 using namespace std;

 const int maxn=;

 int f[maxn+][];

 char s[];

 int t,d;

 int main()

 {

     scanf("%d\n",&t);

     while(t)

     {

         --t;

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

         int n=strlen(s);

         memset(f,,sizeof(f));

         int m=(<<n) - ;

         for(int i=;i<n;++i) f[<<i][(s[i]-)%d]=;

         for(int i=;i<=m;++i)

             for(int j=;j<n;++j)

                 if((i&(<<j))!=  && i-(<<j)>=)

                     for(int k=;k<d;++k)

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

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

         {

             int ans=;

             for(int j=;j<n;++j)

                 if(s[j]-==i) ++ans;

             int c=;

             for(int j=;j<=ans;++j) c*=j;

             f[m][]/=c;

         }

         printf("%d\n",f[m][]);

     }

     return ;

 }