#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    string s, t;
    cin >> s >> t;
    vector<int> fs(26);
    for (char c : s) {
        fs[c - 'a']++;
    }
    vector<int> ft(26);
    for (char c : t) {
        ft[c - 'a']++;
    }
    int mn = 1e9;
    for (int i = 0; i < 26; i++) {
        if (ft[i] > 0) {
            mn = min(mn, ft[i]);
        }
    }
    vector<int> a(26);
    for (int i = 0; i < 26; i++) {
        a[i] = ft[i] / mn;
        ft[i] %= mn;
    }
    int c = 1e9;
    for (int i = 0; i < 26; i++) {
        if (a[i] == 0) continue;
        c = min(c, fs[i] / a[i]);
    }
    int ans = max(0, c - mn);
    bool ok = c >= mn;
    for (int i = 0; i < 26; i++) {
        if (ft[i] > fs[i] - a[i] * c) {
            ok = 0;
        }
    }
    if (ok) ans++;

    vector<int> cntT(26, 0), cntS(26, 0);
    for(char c : t){
        cntT[c - 'a']++;
    }
    for(char c : s){
        cntS[c - 'a']++;
    }
    int len = 0;
    for(int i = 0; i < 26; i++){
        len += cntT[i] / 2;
    }
    int res = 0;
    bool yes = 1;

    for(int i = 0; i < 26; i++){
        yes &= (cntS[i] >= cntT[i]);
    }
    if(yes){
        res++;
        for(int i = 0; i < 26; i++){
            cntS[i] -= cntT[i];
        }
    }
    int n = t.size();
    for(int i = 0; i < 26; i++){
        cntT[i] -= cntT[i] / 2;
    }
    int men = 1e9;
    for(int i = 0; i < 26; i++){
        men = min(men, cntS[i] / cntT[i]);
    }
    res += mn;
    ans = max(ans, res);
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}