又颓废了一个下午，最近撸mc撸到丧失意识了，玩的有点恶心，于是找水题做，瞧不起颓废的自己啊。
another水题。
这题题意很明显啦，就是找数字排列后组成的数去mod d=0后有多少种。
普通的搜索的话，是会tle的（应该是o（n！）没错？）。注意到长度n还是比较小的，于是想到状压dp。
状态就是每个数取和不取组成的结果（就是00110表示第3,4个数取了啦，学过状压都知道）。
然后转移就是f[i,j,k]表示现在取到第i个数状态为i余数为j有多少种情况，
那么f[i,j,(k*10+a[i])mod d]=Σf[i-1，j',k]（也就是同余的东西啦，在123后加一个数字4，那么1234 mod d=（（123 mod d *10）+4 ）mod d ）。k的范围就是0-（d-1）啦。其实就是一个01背包，然后i是可以去掉的。
最后就是处理重复的问题了，之前好像也做过类似的，不过反过来的……重复的话可以这么想，比如有4个2重复，那么对于第4个2来说，加上它后重复的情况就是之前的情况*4，对于第三个2来说，加上它后重复的情况就是之前的情况*3，对于第二个2就是之前的情况*2（其实就是个排列组合……四个2有序号要比没有序号多A（4,4)=4！）。
var
b:array[..,..]of longint;
c,a:array[..]of longint;
f:array[..,..]of longint;
i,j,k,l,n,m,t,tot,top:longint; procedure into;
var
i,j,k,len:longint;
s:string;
begin
readln(s);
len:=length(s);
i:=pos(' ',s);
val(copy(s,i+,len-i),tot);
delete(s,i,len-i+);
n:=length(s);
fillchar(c,sizeof(c),);
for i:= to n do begin
a[i]:=ord(s[i])-ord('');
inc(c[a[i]]);
end;
top:=<<n-;
fillchar(b,sizeof(b),);
for i:= to top do begin
j:=i;
k:=;
while j<> do begin
inc(k);
dec(j,j and (-j));
end;
j:=k;
inc(b[j,]);
b[j,b[j,]]:=i;
end;
end; procedure work;
var
i,j,k,l,m,ans:longint;
begin
fillchar(f,sizeof(f),);
for i:= to n do
f[<<(i-),a[i] mod tot]:=;
for i:= to n do
for j:= to b[i,] do begin
k:=b[i,j];
for l:= to n do
if k and (<<(l-)) <> then
for m:= to tot- do
inc(f[k,(*m+a[l]) mod tot],f[k-<<(l-),m]);
end;
ans:=f[top,];
for i:= to do
if c[i]> then
for j:= to c[i] do ans:=ans div j;
writeln(ans);
end; begin
readln(t);
while t> do begin
dec(t);
into;
work;
end;
end.