#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int z;
    cin >> z;
    while (z--) {
        string s, t;
        cin >> s >> t;
        vector<ll> cnts(26), cntt(26);
        for (char c : s) {
            ++cnts[c - 'a'];
        }
        for (char c : t) {
            ++cntt[c - 'a'];
        }
        int g = 0;
        rep(c, 0, 26) { g = gcd(g, cntt[c]); }
        if (g == 1) {
            ll lb = 0, ub = 1e9;
            while (ub - lb > 1) {
                int m = (lb + ub) / 2;

                bool ok = true;
                rep(c, 0, 26) {
                    ll tt = (cntt[c] / 2) * (m + 1) + (cntt[c] % 2) * m;
                    if (cnts[c] < tt) {
                        ok = false;
                        break;
                    }
                }
                if (ok)
                    lb = m;
                else
                    ub = m;
            }
            cout << lb << "\n";
        } else {
            ll maxA = 1e9;
            rep(c, 0, 26) {
                if (cntt[c] != 0) {
                    chmin(maxA, cnts[c] / (cntt[c] / g));
                }
            }
            cout << max(0LL, maxA - g + 1) << "\n";
        }
    }
}