#include <bits/stdc++.h>
using namespace std;

#define int long long

using ll = long long;
using i64 = long long;
using pii = pair<int, int>;
using db = double;

#define cY cout << "YES\n"
#define cN cout << "NO\n"
#define cA cout << ans << "\n"
#define pb push_back

const int N = 2e5 + 7;
const ll mod = 998244353;
const ll MOD = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

void crossparallel() {
    string s, t;
    cin >> s >> t;

    vector<int> cs(26), ct(26);
    for (auto i : s) cs[i - 'a']++;
    for (auto i : t) ct[i - 'a']++;

    for (int i = 0; i < 26; i++) {
        if (cs[i] < ct[i]) {
            cout << 0 << "\n";
            return;
        }
        cs[i] -= ct[i];
    }

    for (int p = t.length(); p > 0; p--) {
        int ans = s.length(), flg = 0;
        for (int i = 0; i < 26; i++) {
            if (ct[i] == 0)
                continue;
            if (((ct[i] + p - 1) / p) * (p - 1) > ct[i])
                flg++;
            ans = min(ans, cs[i] / ((ct[i] + p - 1) / p));
        }
        if (!flg) {
            cout << ans + 1 << "\n";
            return;
        }
    }

    return;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        crossparallel();
    }
    return 0;
}