/*
    author:  Maksim1744
    created: 21.10.2023 12:57:03
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

mt19937_64 rng(478236);
ll rnd (ll l, ll r) { return (ll)(rng() % (r - l + 1)) + l; }
ll rnd (ll r)       { return rng() % r; }
ll rnd ()           { return rng(); }
ld rndf()           { return (ld)rng() / (ld)ULLONG_MAX; }
ld rndf(ld l, ld r) { return rndf() * (r - l) + l; }

void test_case(int test) {
    string t, s;
    cin >> t >> s;
    array<int, 26> ct{}, cs_{};
    for (char c : t)
        ct[c - 'a']++;
    for (char c : s)
        cs_[c - 'a']++;
    for (int i = 0; i < 26; ++i) {
        ct[i] -= cs_[i];
        if (ct[i] < 0) {
            cout << 0 << '\n';
            return;
        }
    }
    show(ct);

    int n = s.size();
    vector<int> lens(n - 1);
    iota(lens.begin(), lens.end(), 1);
    shuffle(lens.begin(), lens.end(), rng);
    int ans = 1e9;
    for (int i = 0; i < 26; ++i)
        if (cs_[i])
            ans = min(ans, ct[i] / cs_[i]);
    for (int p : lens) {
        shows;
        show(p);
        int classlen = n / p;
        int k = n % p;
        auto cs = cs_;
        array<int, 26> per{};
        bool ok = true;
        for (int i = 0; i < 26; ++i) {
            int& x = cs[i];
            int r = x % classlen;
            if ((ll)(classlen + 1) * r > x) {
                ok = false;
                break;
            }
            x -= (classlen + 1) * r;
            assert(x % classlen == 0);
            per[i] += r;
            k -= r;
        }
        if (!ok) continue;
        if (k < 0) continue;
        assert(k % classlen == 0);

        show(cs);
        show(per);
        show(k);
        show(classlen);

        auto K = k;
        auto can = [&](int cnt) {
            auto k = K;
            show(cnt, k);
            auto ccs = cs;
            for (int i = 0; i < 26; ++i) {
                if (ct[i] / cnt < per[i]) return false;
                int left = ct[i] - cnt * per[i];
                int needsub = ccs[i] / classlen - left / cnt;
                if (needsub <= 0) continue;
                if (ccs[i] / classlen / (classlen + 1) < needsub) return false;
                ccs[i] -= needsub * classlen * (classlen + 1);
                k -= needsub * classlen;
                if (k < 0) return false;
            }
            show(k);
            show(ccs);
            for (int& x : ccs) {
                int cansub = x / classlen / (classlen + 1);
                cansub = min(cansub, k / classlen);
                x -= cansub * classlen * (classlen + 1);
                k -= cansub * classlen;
            }
            show(k);
            show(ccs);
            return k == 0;
        };
        if (!can(ans + 1)) continue;
        int l = ans + 1;
        int r = t.size() + 1;
        while (r - l > 1) {
            int c = (l + r) / 2;
            if (can(c))
                l = c;
            else
                r = c;
        }
        show(l);
        ans = max(ans, l);
    }
    cout << ans + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T;
    cin >> T;
    for (int test = 1; test <= T; ++test) {
        test_case(test);
    }

    return 0;
}