#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN = 11;

int T,d,a[MAXN],cnt,dp[1<<MAXN][1002];
bool b[MAXN];
char s[MAXN];

int main(){
	scanf("%d",&T);int len;
	while(T--){
		memset(dp,0,sizeof(dp));
		scanf("%s%d",s+1,&d);
		len=strlen(s+1);cnt=0;
		for(register int i=1;i<=len;i++) a[i]=s[i]-'0';//把所有数字存一下
		dp[0][0]=1;  //赋初值
		for(register int S=0;S<(1<<len)-1;S++){ //S表示当前所选的状态集合
			memset(b,0,sizeof(b));  //注意清零
			for(register int j=1;j<=len;j++)if(!(S&(1<<(j-1))) && !b[a[j]]){ //如果a[j]已经转移过就不能继续转移了,j表示遍历s中的各位数字。
				b[a[j]]=1;
				for(register int k=0;k<d;k++) //k表示对d取余后的数
					dp[S|(1<<(j-1))][(k*10+a[j])%d]+=dp[S][k];
			}
		}
		printf("%d\n",dp[(1<<len)-1][0]);
	}
	return 0;
}