1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int t,d,n,tot[15],f[2005][1005];

 4 char s[15];

 5 int main(){

 6     scanf("%d",&t);

 7     while (t--){

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

 9         n=strlen(s);

10         memset(tot,0,sizeof(tot));

11         for(int i=0;s[i];i++)tot[s[i]-'0']++;

12         memset(f,0,sizeof(f));

13         f[0][0]=1;

14         for(int i=0;i<(1<<n);i++)

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

16                 if (!(i&(1<<j)))

17                     for(int k=0;k<d;k++){

18                         int kk=(k*10+s[j]-'0')%d;

19                         f[i+(1<<j)][kk]=f[i+(1<<j)][kk]+f[i][k];

20                     }

21         for(int i=0;i<10;i++)

22             for(int j=1;j<=tot[i];j++)f[(1<<n)-1][0]/=j;

23         printf("%d\n",f[(1<<n)-1][0]);

24     }

25 }