#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A, class B> void cmx(A& x, B y){ x = max<A>(x,y); }
template<class A, class B> void cmn(A& x, B y){ x = min<A>(x,y); }
typedef pair<int,int> pii;
typedef vector<int> vi;

int ceil(int a, int b) {
    return (a + (b-1)) / b;
}

int l[200], l1[200], l2[200], pl[200];

void fun() {
    string slo, wzo;
    cin >> slo >> wzo;
    for (char c = 'a'; c <= 'z'; c++) {
        l[c] = 0;
        pl[c] = 0;
    }
    for (auto c : slo) {
        pl[c]++;
    }
    for (auto c : wzo) {
        l[c]++;
    }
    int res = 1;
    for (char c = 'a'; c <= 'z'; c++) {
        if (l[c] > pl[c])
            res = 0;
    }
//    cerr << "test\n\n";
    for (int x = 1; x <= sz(wzo); x++) {
        int ok = 1;
        for (char c = 'a'; c <= 'z'; c++) {
            l1[c] = ceil(l[c], (x+1));
            l2[c] = l[c] - x * l1[c];
            if (l2[c] < 0) {
                ok = 0;
            }
        }
//        cout << x << " " << ok << "\n";
//        cout << l1['a'] << " " << l1['l'] << "\n";
//        cout << l2['a'] << " " << l2['l'] << "\n";
//        cout << l['a'] << " " << l['l'] << "\n";
        if (!ok)
            continue;
        int cykle = 10000000, reszta = 1;
        for (char c = 'a'; c <= 'z'; c++) {
            if (l1[c] == 0) {
                continue;
            }
            cmn(cykle, pl[c] / l1[c]);
        }
        for (char c = 'a'; c <= 'z'; c++) {
            reszta &= pl[c] - l1[x] * cykle >= l2[c];
        }
//        cout << x << " " << cykle << " " << reszta << "\n\n";
        cmx(res, cykle - x + reszta);
    }
    cout << res << "\n";
}

signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    int t;
    cin >> t;
    while (t--) fun();
}