// clang-format off
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <bitset>
#include <vector>
#include <algorithm>
#include <random>
#include <map>
#include <string>
#include <set>
#include <deque>
#include <cassert>

const int N = 2e5 + 7, A = 26, C = 2, MOD = 998244353;
using namespace std;
using ll = long long;
using ld = long double;

const ld EPS = 1e-9;

long long b;

string n;

set<long long> dp;

long long cnt(int len, int b) {
    long long cnt = 9 / b;
    for (int i = 0; i < len-1; i++) {
        cnt *= (9 / b + 1);
    }
    return cnt;
}

long long binpow(long long x, long long step) {
    if (step == 0) {
        return 1;
    }
    if (step % 2) {
        return x * binpow(x, step - 1);
    }
    long long h = binpow(x, step / 2);
    return h * h;
}

long long cnt2(string s, int b) {
    long long answ = 0;
    for (int i = 0; i < s.size(); i++) {
        for (int c = 0; c < s[i] - '0'; c += b) {
            if (i == 0 && c == 0) {
                continue;
            }
            answ += binpow((9 / b + 1), s.size() - 1 - i);
        }
        if ((s[i] - '0') % b != 0) {
            break;
        }
    }
    return answ;
}

void solve() {
    cin >> n >> b;
    long long answ = 0;
    for (int len = 1; len < n.size(); len++) {
        answ += cnt(len, b);
    }
    answ += cnt2(n, b);
    int f = 1;
    for (int i = 0; i < n.size(); i++) {
        if ((n[i] - '0') % b != 0) {
            f = 0;
        }
    }
    cout << answ + f<< "\n";
}

signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#else
    std::ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}