Description

　　给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。例如123434有90种排列能

被2整除，其中末位为2的有30种，末位为4的有60种。

Input

　　输入第一行是一个整数T，表示测试数据的个数，以下每行一组s和d，中间用空格隔开。s保证只包含数字0,

, , , , , , , , .

Output

　　每个数据仅一行，表示能被d整除的排列的个数。

Sample Input

Sample Output

HINT

在前三个例子中，排列分别有1, , 3628800种，它们都是1的倍数。

【限制】

%的数据满足：s的长度不超过10, <=d<=, <=T<=

Source

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

char s[];

int t;

ll d;

ll dp[ << ][];

ll num[],p[];

int main()

{

    read(t);

    while(t--)

    {

        clean(dp);clean(num);clean(p);

        scanf("%s",s + );

        int l = strlen(s + );

//        cout<<l<<endl;

        duke(i,,l)

        num[s[i] - '']++,p[i] = s[i] - '';

        read(d);

        dp[][] = ;

        duke(i,,( << l) - )

        {

            duke(j,,d - )

            {

                duke(k,,l)

                {

                    if((i & ( << (k - ))) == )

                    {

                        dp[i | ( << (k - ))][(j *  + p[k]) % d] += dp[i][j];

                    }

                }

            }

        }

//        cout<<"QAQ"<<endl;

        ll ans = dp[( << l) - ][];

        duke(i,,)

        {

            duke(j,,num[i])

            ans /= j;

        }

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

    }

    return ;

}

/*

7

000 1

001 1

1234567890 1

123434 2

1234 7

12345 17

12345678 29

*/