#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

void XORFFT(int a[], int n, int p, int invert) {
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; k++) {
                int u = a[j + k], v = a[i + j + k];
                a[j + k] = u + v;
                if (a[j + k] >= p) a[j + k] -= p;
                a[i + j + k] = u - v;
                if (a[i + j + k] < 0) a[i + j + k] += p;
            }
        }
    }
    if (invert) {
        long long inv = fpow(n, p - 2, p);
        for (int i = 0; i < n; i++) a[i] = a[i] * inv % p;
    }
}

struct data_t {
    int vals[16][1 << 10];
    data_t() {
        ms(vals, 0);
    }
    int* operator [] (int i) {
        return vals[i];
    }
};

data_t unit() {
    data_t res;
    res[0][0] = 1;
    return res;
}

int s, p, q;
long long k;
int f[7][17][17][1 << 10];
int g[7][17][17][1 << 10];

data_t operator + (data_t a, data_t b) {
    data_t res;
    FOR(i, 0, p) FOR(j, 0, 1 << 10) {
        res[i][j] = a[i][j];
        addmod(res[i][j], b[i][j]);
    }
    return res;
}

data_t operator * (data_t a, data_t b) {
    data_t res;
    static int fa[16][1 << 10];
    static int fb[16][1 << 10];
    static int fc[16][1 << 10];
    FOR(i, 0, p) {
        FOR(j, 0, 1 << 10) {
            fa[i][j] = a[i][j];
            fb[i][j] = b[i][j];
        }
        XORFFT(fa[i], 1 << 10, MOD, 0);
        XORFFT(fb[i], 1 << 10, MOD, 0);
    }
    FOR(i, 0, p) FOR(j, 0, 1 << 10) fc[i][j] = 0;
    FOR(i, 0, p) FOR(j, 0, p) {
        FOR(k, 0, 1 << 10) {
            addmod(fc[(i + j) % p][k], mult(fa[i][k], fb[j][k]));
        }
    }
    FOR(k, 0, p) {
        XORFFT(fc[k], 1 << 10, MOD, 1);
        FOR(i, 0, 1 << 10) {
            addmod(res[k][i], fc[k][i]);
        }
    }
    return res;
}

data_t pow(data_t a, long long k) {
    if (k == 1) return a;
    if (k & 1) return pow(a, k - 1) * a;
    data_t t = pow(a, k >> 1);
    return t * t;
}

data_t series(data_t a, long long k) {
    if (!k) return unit();
    if (k == 1) return a + unit();
    vector<int> bit;
    while (k) {
        bit.push_back(k & 1);
        k >>= 1;
    }
    data_t res = a, tmp = a;
    for (int i = bit.size() - 2; i >= 0; i--) {
        res = res + (res * tmp);
        tmp = tmp * tmp;
        if (bit[i] & 1) {
            tmp = tmp * a;
            res = res + tmp;
        }
    }
    res = res + unit();
    return res;
}

template<class T> pair<T, T> euclid(T a, T b) {
    if (!b) return make_pair(1, 0);
    pair<T, T> r = euclid(b, a % b);
    return make_pair(r.second, r.first - a / b * r.second);
}

int inverse(int a, int b) {
    pi r = euclid(a, b);
    return (r.fi % b + b) % b;
}

void chemthan() {
    int pp = 1;
    FOR(k, 1, 6 + 1) {
        pp *= 10;
        FOR(i, 0, pp) {
            int msk = 0, t = i;
            FOR(j, 0, k) msk ^= 1 << t % 10, t /= 10;
            FOR(d, 1, 16 + 1) {
                f[k][d][i % d][msk]++;
            }
        }
        FOR(i, pp / 10, pp) {
            int msk = 0, t = i;
            FOR(j, 0, k) msk ^= 1 << t % 10, t /= 10;
            FOR(d, 1, 16 + 1) {
                g[k][d][i % d][msk]++;
            }
        }
    }
    int test; cin >> test;
    assert(1 <= test && test <= 20);
    while (test--) {
        cin >> s >> k;
        assert(1 <= s && s <= 16);
        assert(1 <= k && k <= 1e18);
        p = s, q = 1;
        while (p % 2 == 0) {
            p /= 2, q *= 2;
        }
        while (p % 5 == 0) {
            p /= 5, q *= 5;
        }
        if (k <= 4) {
            int res = 1;
            FORd(i, fpow(10, k), 1) if (i % s == 0) {
                int msk = 0, t = i;
                while (t) msk ^= 1 << t % 10, t /= 10;
                if (bitcount(msk) <= 1) {
                    res++;
                }
            }
            cout << res << "\n";
            continue;
        }
        k -= 4;
        int res = 1;
        FORd(i, fpow(10, 4), 1) if (i % s == 0) {
            int msk = 0, t = i;
            while (t) msk ^= 1 << t % 10, t /= 10;
            if (bitcount(msk) <= 1) {
                res++;
            }
        }
        data_t block;
        FOR(i, 0, p) FOR(j, 0, 1 << 10) block[i][j] = f[6][p][i][j];
        data_t x = series(block, (k - 1) / 6);
        data_t y;
        if ((k - 1) / 6 > 0) {
            y = series(block, (k - 1) / 6 - 1);
        }
        FOR(r, 1, 6 + 1) {
            if (k >= r) {
                data_t head;
                FOR(i, 0, p) FOR(j, 0, 1 << 10) head[i][j] = g[r][p][i][j];
                data_t join;
                if ((k - r) / 6 == (k - 1) / 6) {
                    join = head * x;
                }
                else {
                    join = head * y;
                }
                FOR(i, 0, s) {
                    if (i % q == 0) {
                        int need = p == 1 ? 0 : mult(p - i % p, inverse(10000, p), p);
                        assert(((long long) need * 10000 + i) % p == 0);
                        FOR(j, 0, 1 << 10) {
                            addmod(res, mult(join[need][j], f[4][s][i][j]));
                            FOR(l, 0, 10) {
                                addmod(res, mult(join[need][j ^ (1 << l)], f[4][s][i][j]));
                            }
                        }
                    }
                }
            }
        }
        cout << res << "\n";
    }
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}