#include <bits/stdc++.h>

 #define range(i,c,o) for(register int i=(c);i<(o);++i)

 #define dange(i,c,o) for(register int i=(c);i>(o);--i)

 using namespace std;

 //#define __debug

 #ifdef __debug

     #define Function(type) type

     #define Procedure      void

 #else

     #define Function(type) __attribute__((optimize("-O2"))) inline type

     #define Procedure      __attribute__((optimize("-O2"))) inline void

 #endif

 int cnt[],tmp[];

 Function(int) status()

 {

     int ret=;

     range(i,,) (ret*=cnt[i]+)+=tmp[i];

     return ret;

 }

 static int T,n,AwD; int f[][][];

 int DFS(const int&k,const int&r)

 {

     if(k==n) return !r; int S=status();

     if(~f[k][r][S]) return f[k][r][S];

     f[k][r][S]=;

     range(i,,) if(tmp[i])

     {

         --tmp[i];

         f[k][r][S]+=DFS(k+,(r*+i)%AwD);

         ++tmp[i];

     }

     return f[k][r][S];

 }

 char s[];

 int main()

 {

     for(scanf("%d",&T);T--;)

     {

         scanf("%s%d",s,&AwD),n=strlen(s);

         memset(cnt,,sizeof cnt);

         range(i,,n) ++cnt[s[i]-''];

         memcpy(tmp,cnt,sizeof tmp);

         memset(f,-,sizeof f);

         printf("%d\n",DFS(,));

     }

     return ;

 }