#include <bits/stdc++.h>
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#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()
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

const int MAXN = 2100000;
char s[MAXN], t[MAXN];

void solve() {
    scanf("%s%s", s, t);
    int ns = strlen(s), nt = strlen(t);
    vector<int> cnts(26, 0), cntt(26, 0);
    rep(i,0,ns) cnts[s[i]-'a']++;
    rep(i,0,nt) cntt[t[i]-'a']++;
    int ans = 0, minch = 1e9, initct = 1e9;
    rep(i,0,26) if(cntt[i] > 0) {
        minch = min(minch, cntt[i]);
        initct = min(initct, cnts[i]/cntt[i]);
    }
    ans = initct;
    debug(ans);
    for(int nprd = 1; nprd <= minch; ++nprd) {
        int ct = 1e9;
        rep(i,0,26) if(cntt[i]) {
            int prd = (cntt[i]+nprd) / (nprd+1);
            debug(cntt[i],prd,nprd);
            debug(nprd,i,prd);
            int ff;
            if(cnts[i] < cntt[i]) {
                ff = 0;
            } else {
                ff = 1 + (cnts[i]-cntt[i])/prd;
            }
            ct = min(ct, ff);
        }
        ans = max(ans, ct);
    }
    cout << ans << '\n';
}

signed main() {
    int T; read(T);
    while(T--) solve();
    return 0;
}