#include <bits/stdc++.h>

#define N 1005

using namespace std;

void setIO(string s)

{

	string in=s+".in";

	string out=s+".out";

	freopen(in.c_str(),"r",stdin);

	// freopen(out.c_str(),"W",stdout);

}

char str[N];

int num[N],f[N<<1][N],poww[N],tax[11],fac[N],vis[11];

void solve()

{

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

	memset(tax,0,sizeof(tax));

	memset(vis,0,sizeof(vis));

	int mod,i,j,n,k;

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

	n=strlen(str);

	fac[0]=poww[0]=1;

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

	for(i=1;i<=n;++i)   poww[i]=poww[i-1]*10%mod;

	for(i=0;i<n;++i)    num[i]=str[i]-'0', ++tax[num[i]];

	f[0][0]=1;

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

	{

		for(j=0;j<mod;++j)

		{

			int sz=0;

			for(k=0;k<n;++k)   if(i&(1<<k)) ++sz;

			for(k=0;k<n;++k)

			{

				if(i&(1<<k)) continue;

				else

				{

					int nx=i|(1<<k);

					int cur=num[k];

					f[nx][(j+cur*poww[sz]%mod)%mod]+=f[i][j];

				}

			}

		}

	}

	int ans=f[(1<<n)-1][0];

	for(i=0;i<n;++i)   if(!vis[num[i]])   vis[num[i]]=1, ans/=fac[tax[num[i]]];

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

}

int main()

{

	// setIO("input");

	int T;

	scanf("%d",&T);

	while(T--)

	{

		solve();

	}

	return 0;

}