#define _CRT_SECURE_NO_WARNINGS 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
using namespace std; 
const int MAXN = 11; 
//dp[S][k]表示现在所选的状态集合为S，当前所选的数,组成的数字对d取余后的值为k，这样就可以转移了。
//首先枚举所有的状态S，然后再枚举所有没有被选的数j，再枚举余数k即可转移。 
int T, d, a[MAXN], cnt, dp[1 << MAXN][1002]; 
bool b[MAXN];
char s[MAXN];
int PowTwo(int width)  //2的width次方 
{     
    return 1 << width;    
}     
int main() 
{ 
    scanf("%d", &T);  
    int len; 
    while (T--)  
    { 
        memset(dp, 0, sizeof(dp));   //dp数组清零 
        scanf("%s%d", s + 1, &d);   //输入串和除数d 
        len = strlen(s + 1);       //串的长度 
        cnt = 0; 
        for ( int i = 1; i <= len; i++) {  //register使用cpu中央处理器，更加快 
            a[i] = s[i] - '0';     //把所有数字存一下 
        } 
        dp[0][0] = 1;       //赋初值 
        //   1<<len== 2^len    
        for ( int S = 0; S < PowTwo(len)- 1; S++) { //S表示当前所选的状态集合,0 ———— 2^len - 1
            memset(b, 0, sizeof(b));          //注意清零 
            for ( int j = 1; j <= len; j++){     // 1————len
                if (   !( S & PowTwo(j - 1) )  &&  ! b[a[j]]) {  
                //S按位与2^(j-1),按位与1左移j-1位等于0，并且 b[a[j]]=0，没用过 
                    //如果a[j]已经转移过就不能继续转移了,j表示遍历s中的各位数字。 
                    b[ a[j] ] = 1;   //转移了      
                    for ( int k = 0; k < d; k ++ ) {  //k表示对d取余后的数 
                        dp[ S | 1<<(j-1)  ][  (  k * 10 + a[j]  ) % d ] += dp[S][k]; 
                        //符号|是按位或，S按位或2^(j-1)   
                    }  
                } 
            } 
        } 
        printf("%d\n", dp[PowTwo(len) - 1][0]); 
    } 
    return 0; 
}