#include<bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


using ll = long long;
#define int ll
#define endl "\n"
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define pii pair<int,int>
#define ary(i) array<ll,(i)>
#define all(x) x.begin(),x.end()
const int maxn = 2e5 + 7;
const int inf = numeric_limits<int>::max();
const int inf2 = 0x3f3f3f3f3f3f3f3;
const int inff = numeric_limits<int>::min();
const int mod = 1e9 + 7;


void solve() {

    string s1, s2;
    cin >> s1 >> s2;

    vector<int> ns1(26, 0), ns2(26, 0);
    for (auto i: s1) {
        ns1[i - 'a']++;
    }
    for (auto i: s2) {
        ns2[i - 'a']++;
    }
    int mins = inf;
    for (int i = 0; i < 26; i++) {
//        如果存在
        if (ns2[i]) {
//            不能完成
            if (ns2[i] > ns1[i]) {
                cout << 0 << endl;
                return;
            }
//            只有一种字符
            if (ns2[i] == s2.length()) {
                cout << ns1[i] - ns2[i] + 1 << endl;
                return;
            }
//            最小分块数目
            mins = min(ns2[i], mins);
        }
    }
//    计算用于补的情况
    for (int i = 0; i < 26; i++) {
        ns1[i] -= ns2[i];
    }
    int ans = 0;
    for (int i = 1; i <= mins + 1; i++) {
        int minf = inf;
        for (int j = 0; j < 26; j++) {
//            某一个字符串存在
            if (ns2[j]) {
//                上取整 求每一块的数目
                int er = (ns2[j] + i - 1) / i;
//                超过一块补不起
                if (er * i - ns2[j] > er) {
                    ans = 0;
                    break;
                }
                minf = min(minf, ns1[j] / er);
            }
        }
        cerr << minf << " ";
        ans = max(ans, minf + 1);
    }
    cout << ans << endl;
    cerr << endl;

}

#undef int


int main() {
//    IOS
    int n;
    cin >> n;
//    n = 1;
    while (n--) {
        solve();
    }

}