#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) ((int)(x).size())

typedef double db;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define ws laksdaljk
string s, t;
int n, m;
int ss[26];
int ts[26];
int rs[26];
int ws[26];
void solve() {
    memset(ts, 0, sizeof ts);
    memset(ss, 0, sizeof ss);
    cin >> s >> t;
    for (char c : s) ss[c - 'a']++;
    for (char c : t) ts[c - 'a']++;
    int ans=1e9;
    for(int i=0;i<26;i++){
        if(ts[i]){
            if(ss[i]<ts[i])return cout<<"0\n",void();
            ans=min(ans,ss[i]/ts[i]);
        }
    }
    for(int c=1;c<t.size();c++){
        int tmp=1e9;
        for(int i=0;i<26;i++){
            if(ts[i]){
                if(ts[i]<c){
                    tmp=0;break;
                }
                rs[i]=(ts[i]+c)/(c+1);
                tmp=min(tmp,(ss[i]-ts[i])/rs[i]+1);
            }
        }
        ans=max(ans,tmp);
    }
    cout<<ans<<"\n";
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}