#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;

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 mn = INF;
    for(auto cnt : cnt_t) {
        if(cnt) mn = min(mn, cnt);
    }

    mn++;
    for(auto &cnt : cnt_t) {
        cnt = (cnt + mn - 1) / mn;
    }

    mn = INF;
    for(int i = 0; i < 26; i++) {
        if(cnt_t[i]) mn = min(cnt_s[i] / cnt_t[i], mn);
    }

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