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

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) ((int)(x).size())

typedef double db;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define ws laksdaljk
string s, t;
int n, m;
int ss[26];
int ts[26];
int rs[26];
int ws[26];
void solve() {
    memset(ts, 0, sizeof ts);
    memset(ss, 0, sizeof ss);
    cin >> s >> t;
    for (char c : s) ss[c - 'a']++;
    for (char c : t) ts[c - 'a']++;
    int ans = 1e9;
    for (int i = 0; i < 26; i++) {
        if (ts[i]) {
            if (ss[i] < ts[i]) return cout << "0\n", void();
            ans = min(ans, ss[i] / ts[i]);
        }
    }
    for (int c = 1; c <= t.size(); c++) {
        int tmp = 1e9;
        int s=0;
        for (int i = 0; i < 26; i++) {
            if (ts[i]) {
                if (ts[i] < c) {
                    tmp = 0;
                    break;
                }
                rs[i] = (ts[i] + c) / (c + 1);
                s+=rs[i];
                tmp = min(tmp, (ss[i] - ts[i]) / rs[i] + 1);
            }
        }
        if(s*c<=t.size())
        ans = max(ans, tmp);
    }
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}