/* string coder = "Balajiganapathi S"; // Never give up!  */

//#define LOCAL
#ifdef LOCAL
//#   define TRACE
#   define TEST
#else
//#   define NDEBUG
//#   define FAST
#endif

#include<bits/stdc++.h>

using namespace std;

/* aliases */
using vi  = vector<int>;
using pi  = pair<int, int>;
using ll  = long long int;

/* shortcut macros */
#define mp              make_pair
#define fi              first
#define se              second
#define mt              make_tuple
#define gt(t, i)        get<i>(t)
#define all(x)          (x).begin(), (x).end()
#define ini(a, v)       memset(a, v, sizeof(a))
#define rep(i, s, n)    for(int i = (s), _##i = (n); i <= _##i; ++i)
#define re(i, s, n)     rep(i, (s), (n) - 1)
#define fo(i, n)        re(i, 0, n)
#define si(x)           (int((x).size()))
#define is1(mask,i)     (((mask) >> i) & 1)

/* trace macro */
#ifdef TRACE
#   define trace(v...)  {cerr << __func__ << ":" << __LINE__ << ": " ;_dt(#v, v);}
#else
#   define trace(...)
#endif

#ifdef TRACE
pi _gp(string s) {
    pi r(0, si(s) - 1);
    int p = 0, s1 = 0, s2 = 0, start = 1;
    fo(i, si(s)) {
        int x = (s1 | s2);
        if(s[i] == ' ' && start) {
            ++r.fi;
        } else {
            start = 0;
            if(s[i] == ',' && !p && !x) {
                r.se = i - 1;
                return r;
            }
            if(x && s[i] == '\\') ++i;
            else if(!x && s[i] == '(') ++p;
            else if(!x && s[i] == ')') --p;
            else if(!s2 && s[i] == '\'') s1 ^= 1;
            else if(!s1 && s[i] == '"') s2 ^= 1;
        }
    }
    return r;
}

template<typename H> void _dt(string u, H&& v) {
    pi p = _gp(u);
    cerr << u.substr(p.fi, p.se - p.fi + 1) << " = " << forward<H>(v) << " |" << endl;
}

template<typename H, typename ...T> void _dt(string u, H&& v, T&&... r) {
    pi p = _gp(u);
    cerr << u.substr(p.fi, p.se - p.fi + 1) << " = " << forward<H>(v) << " | ";
    _dt(u.substr(p.se + 2), forward<T>(r)...);
}

template<typename T> 
ostream &operator <<(ostream &o, vector<T> v) { // print a vector
    o << "[";
    fo(i, si(v) - 1) o << v[i] << ", ";
    if(si(v)) o << v.back();
    o << "]";
    return o;
}

template<typename T1, typename T2> 
ostream &operator <<(ostream &o, map<T1, T2> m) { // print a map
    o << "{";
    for(auto &p: m) {
        o << " (" << p.fi << " -> " << p.se << ")";
    }
    o << " }";
    return o;
}

template<typename T> 
ostream &operator <<(ostream &o, set<T> s) { // print a set
    o << "{";
    bool first = true;
    for(auto &entry: s) {
        if(!first) o << ", ";
         
        o << entry;
        first = false;
    }
    o << "}";
    return o;
}

template <size_t n, typename... T>
typename enable_if<(n >= sizeof...(T))>::type
    print_tuple(ostream&, const tuple<T...>&) {} 

template <size_t n, typename... T>
typename enable_if<(n < sizeof...(T))>::type
    print_tuple(ostream& os, const tuple<T...>& tup) {
    if (n != 0)
        os << ", ";
    os << get<n>(tup);
    print_tuple<n+1>(os, tup);
}

template <typename... T>
ostream& operator<<(ostream& os, const tuple<T...>& tup) { // print a tuple
    os << "("; print_tuple<0>(os, tup); return os << ")"; } template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { // print a pair
    return os << "(" << p.fi << ", " << p.se << ")";
}
#endif
    
/* util functions */
template<typename T1, typename T2, typename T3>
T1 modpow(T1 _a, T2 p, T3 mod) {
    assert(p >= 0);
    ll ret = 1, a = _a;

#ifndef FAST
    if(a < 0) {
        a %= mod;
        a += mod;
    } 

    if(a >= mod) {
        a %= mod;
    }
#endif

    for(; p > 0; p /= 2) {
        if(p & 1) ret = ret * a % mod;
        a = a * a % mod;
    }

    return ret;
}

#define x1 _asdfzx1
#define y1 _ysfdzy1

/* constants */
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr auto PI  = 3.14159265358979323846L;
constexpr auto oo  = numeric_limits<int>::max() / 2 - 2;
constexpr auto eps = 1e-6;
constexpr auto mod = 1000000007;

/* code */
constexpr int mx_len = 1000005, mx_m = 1004;
string a;
int M;
int preLeft[mx_len], preRight[mx_len], cnt[mx_m];
int ans;
int vis[mx_m];
int len;
int ten_len_1;

void dfs(int x) {
	if(vis[x]) return;
	ans += cnt[x];
	vis[x] = 1;
	trace(x, cnt[x]);

	for(int nxt = 1; nxt < M; ++nxt) if(!vis[nxt]) {
		// calculate req s.t. nxt * 10^(len-1) + req = x (mod M):
		int req = (x + M - nxt * ten_len_1 % M) % M;
		trace(x, nxt, req, cnt[req], (nxt * ten_len_1 + req) % M);
		assert((nxt * ten_len_1 + req) % M == x);
		if(cnt[req] > 0) dfs(nxt); // req must be a possible move
	}
}

int main() {
	int t, sum_len = 0;
	assert(cin >>  t);
	assert(1 <= t && t <= 100);
	while(t--) {
		assert(cin >> a);
		len = si(a);
		assert(2 <= len && len <= 1000000);
		sum_len += len;
		assert(sum_len <= 5000000);
		assert(cin >> M);
		assert(1 <= M && M <= 1000);
		fo(i, len) assert(isdigit(a[i]));

		int sofar = 0;
		fo(i, len) {
			sofar = (10 * sofar + a[i] - '0') % M;
			preLeft[i] = sofar;
		}

		sofar = 0;
		int p10 = 1;
		for(int i = len - 1; i >= 0; --i) {
			int d = a[i] - '0';
			sofar = (sofar + p10 * d) % M;
			preRight[i] = sofar;
			p10 = 10 * p10 % M;
		}

		p10 = 1;
		ini(cnt, 0);
		for(int i = len - 1; i >= 0; --i) {
			int fromLeft = 0, fromRight = 0;
			if(i > 0) fromLeft = preLeft[i-1];
			if(i < len - 1) fromRight = preRight[i+1];
			int x = (fromLeft * p10 + fromRight) % M;
			trace(i, fromLeft, fromRight, x);
			++cnt[x];
			p10 = 10 * p10 % M;
		}

		ten_len_1 = modpow(10, len - 1, M);
		trace(len, ten_len_1);
		ans = 0;
		ini(vis, 0);
		dfs(0);
		assert(ans == len || ans == 0);

		cout << ans << endl;
	}
    
    
	return 0;
}