#include<stdio.h>
#include<algorithm>
inline int strlen(register char a[]){register int i=0;while(1){if(a[i]=='\0'){return i;}i++;}}
#pragma GCC optimize(0,1,2,3,"Ofast","inline","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-fwhole-program","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-fstrict-overflow","-falign-functions","-fcse-skip-blocks","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","-funsafe-loop-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks")
struct In{template<typename T>inline In&operator>>(T&x){x=0;bool f=1;register char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')f=0;for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);x=f?x:-x;return*this;}}in;
int main(){
	int t;
	in>>t;
    while(t--){
		register char s[15];
        scanf("%s",s);
        register int n,a[15];
        in>>n;
        for(register int i=1;s[i-1];i++){
        	a[i]=s[i-1]-48;
		}
        std::sort(a+1,a+strlen(s)+1);
        register long long ans=0,tmp=0;
        for(register int i=1;s[i-1];i++){
        	tmp=tmp*10+a[i];
		}
        ans+=!(tmp%n);
        while(std::next_permutation(a+1,a+strlen(s)+1)){
			tmp=0;
            for(register int i=1;s[i-1];i++){
            	tmp=tmp*10+a[i];
			}
            ans+=!(tmp%n);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

第一个点过不掉，TLE