#include "bits/stdc++.h"

using namespace std;

using lint = int64_t;
const int base1 = 31, base2 = 37;
const int mod = 1e9 + 7;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t_;
    cin>>t_;
    while(t_--){
        string s, t;
        cin>>s>>t;
        int n = (int)s.size(), m = (int)t.size();
        vector<int>fs(26), ft(26);
        for(char ch : s) fs[ch - 'a']++;
        for(char ch : t) ft[ch - 'a']++;
        vector<int>need(26);
        for(int i=0;i<26;i++) need[i] = ft[i] - ft[i] / 2;
        int ans = 0;
        int c = 0;
        for(int i=0;i<26;i++) c += ft[i] > 0;
        if(c == 1){
            for(int i=0;i<26;i++){
                if(ft[i]) ans = max(ans, max(0, fs[i] - ft[i] + 1));
            }
        }
        else{
            while(true){
                int exceed = 0;
                for(int i=0;i<26;i++){
                    if(ans) fs[i] -= need[i];
                    else fs[i] -= ft[i];
                    if(fs[i] < 0) exceed++;
                }
                if(exceed) break;
                ans++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}