#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[(1<<10)+5][1005],h[15];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,d;
	cin>>n;
	string s;
	while(n--){
		cin>>s>>d;
		int ss=s.size();
		dp[0][0]=1;
		for(int i=0;i<(1<<ss);++i){
			for(int j=0;j<d;++j){
				for(int k=0;k<ss;++k){
					if(!(i&(1<<k))){
						dp[i+(1<<k)][(10*j+(s[k]-'0'))%d]+=dp[i][j];
					}
				}
			}
		}int ans=dp[(1<<ss)-1][0];
		for(int i=0;i<ss;++i){
			++h[(s[i]-'0')];
		}for(int i=0;i<10;++i){
			if(h[i]>1){
				for(int j=1;j<=h[i];++j){
					ans/=j;
				}
			}
		}cout<<ans<<endl;
	}
    return 0;
}