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