#include<bits/stdc++.h>
using namespace std;
#define V vector
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
#define fi first
#define se second
#define all1(x) (x).begin() + 1, (x).end()
#define all0(x) (x).begin(), (x).end()
#define pb push_back

const int INF = 2e9 + 1000;

LL get(LL x, LL y) {
    LL p = x / y;
    LL res = x % y;
    //a * y + b * (y + 1);
    LL a = p - res, b = res;
    LL t = (0 - a) / (y + 1);
    a += t * (y + 1);
    b -= t * (y);
    if(a < 0) a += y + 1, b -= y;
    
    if(b < 0) return -1;
    return a + b;
}

void solve() {
    string s, t; cin >> s >> t;
    V<int> cnt_s(26);
    V<int> cnt_t(26);
    V<int> cost_t(26);

    for(auto c : s) cnt_s[c - 'a']++;
    for(auto c : t) cnt_t[c - 'a']++;

    for(int i = 0; i < 26; i++) {
        cnt_s[i] -= cnt_t[i];
        if(cnt_s[i] < 0) {
            cout << 0 << endl;
            return;
        }
    }

    int ans = 0;

    for(int i = 1; i <= t.size(); i++) {
        int mn = INF;
        bool ok = 1;
        for(int j = 0; j < 26; j++) {
            if(cnt_t[j] == 0) continue;
            int g = get(cnt_t[j], i);
            if(g == -1) ok = 0;
            // cout << "g : " << t[j] << " " << i << " " << g << endl;
            mn = min(mn, cnt_s[j] / g);
        }
        // cout << i << " " << ok << endl;
        if(ok) {
            // cout << "i , mn : " << i << " " << mn << endl;
            ans = max(mn, ans);
        }
    }

    cout << ans + 1 << endl;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t; cin >> t;
    while(t--)
    solve();
}