#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        string s, t;
        cin >> s >> t;
        const int m = t.size();
        int cnt1[26]{}, cnt2[26]{};
        for(auto c : s) cnt1[c - 'a'] += 1;
        for(auto c : t) cnt2[c - 'a'] += 1;
        bool ok = true;
        for(int i = 0; i < 26; i++){
            if (cnt1[i] < cnt2[i]){
                ok = false;
                break;
            }
            cnt1[i] -= cnt2[i];
        }
        if (!ok){
            cout << 0 << '\n';
            continue;
        }
        int ans = 1;
        for(int i = 1; i <= m; i++){
            int d = (m + i - 1) / i;
            int k = d * i - m;
            int sum = 0;
            int cnt3[26]{};
            memcpy(cnt3, cnt2, sizeof cnt3);
            for(int j = 0; j < 26; j++){
                int t = cnt2[j];
                if (t % d != 0){
                    sum += d - t % d;
                    cnt3[j] += d - t % d;
                }
                cnt3[j] /= d;
            }
            if (sum != k) continue;
            int mn = 1e9;
            for(int j = 0; j < 26; j++){
                if (cnt3[j]) mn = min(mn, cnt1[j] / cnt3[j]);
            }
            ans = max(ans, 1 + mn);
        }
        cout << ans << '\n';
    }

}