#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']++;

    int ans = s.length();

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

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

    cA;

    return;
}

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