#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

char s[N], t[N];

int cnt[30], c[30];

void solve() {
    memset(cnt, 0, sizeof(cnt));
    memset(c, 0, sizeof(c));
    cin >> s >> t;
    for (int i = 0; s[i]; i++) cnt[s[i] - 'a']++;
    for (int i = 0; t[i]; i++) c[t[i] - 'a']++;
    int ans = 1;
    for (int i = 0; i < 26; i++) {
        cnt[i] -= c[i];
        if (cnt[i] < 0) ans--;
    }
    if (ans <= 0) {
        cout << ans << "\n";
        return ;
    }
    for (int k = 1; ; k++) {
        bool flag = true, pd = true; 
        for (int i = 0; i < 26; i++) {
            if (k > c[i] + 1) flag = false;
            int s = (c[i] + k - 1) / k;
            if (s * (k - 1) > c[i]) pd = false;
        }
        if (!flag) break;
        if (pd) {
            int Min = 0x3f3f3f3f;
            for (int i = 0; i < 26; i++) if (c[i]) {
                Min = min(Min, cnt[i] / ((c[i] + k - 1) / k));
            }
            if (Min != 0x3f3f3f3f) ans = max(ans, 1 + Min);
        }
    }
    cout << ans << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int T = 1; cin >> T;
    while (T--) solve();
    return 0;
}