#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < n; i += 1)
#define len(a) ((int)(a).size())


const ll inf = 1e18;
mt19937 rnd(234);


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    rep(itr, t) {
        string s, t;
        cin >> s >> t;
        array<int, 26> cs, ct;
        cs.fill(0); ct.fill(0);
        for (auto x : s) cs[x - 'a'] += 1;
        for (auto x : t) ct[x - 'a'] += 1;
        int result = 0;
        bool ok = true;
        rep(i, 26) if (cs[i] < ct[i]) ok = false;
        if (!ok) {
            cout << 0 << "\n";
            continue;
        }
        for (int k = 1; k <= len(t); k += 1) {
            int blocks = len(t) / k;
            int last_block = len(t) % k;
            int rest = last_block;
            array<int, 26> cur_in_block, cur_in_last_block;
            bool ok = true;
            rep(i, 26) {
                cur_in_block[i] = ct[i] / blocks;
                cur_in_last_block[i] = ct[i] % blocks;
                if (cur_in_last_block[i] > cur_in_block[i]) ok = false;
                rest -= cur_in_last_block[i];
            }
            if (!ok or rest < 0 or rest % blocks != 0) continue;
            for (int i = 0; i < rest / blocks; i += 1) {
                int mn = len(s) + 1;
                int mnj = -1;
                rep(j, 26) {
                    if (cur_in_block[j] == 0) continue;
                    if (cur_in_block[j] - 1 < cur_in_last_block[j] + blocks) continue;
                    assert(cs[j] - cur_in_last_block[j] >= 0);
                    int val = (cs[j] - cur_in_last_block[j]) / cur_in_block[j];
                    if (val < mn) {
                        mn = val;
                        mnj = j;
                    }
                }
                if (mnj == -1) {
                    ok = false;
                    break;
                }
                cur_in_block[mnj] -= 1;
                cur_in_last_block[mnj] += blocks;
            }
            if (!ok) continue;
            int cur_result = len(s) + 1;
            rep(j, 26) {
                if (cur_in_block[j] == 0) {
                    assert(cur_in_last_block[j] == 0);
                    continue;
                }
                cur_result = min(cur_result, (cs[j] - cur_in_last_block[j]) / cur_in_block[j] - blocks + 1);
            }
            result = max(result, cur_result);
        }
        cout << result << "\n";
    }
    return 0;
}