#include<bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


using ll = long long;
#define int ll
#define endl "\n"


#define pii pair<int,int>
#define ary(i) array<ll,(i)>
#define all(x) x.begin(),x.end()
const int maxn = 2e5 + 7;
const int inf = numeric_limits<int>::max();
const int inf2 = 0x3f3f3f3f3f3f3f3;
const int inff = numeric_limits<int>::min();
const int mod = 1e9 + 7;


void solve() {
    string a, b;
    cin >> a >> b;
    vector<int> an(26, 0);
    vector<int> bn(26, 0);
    vector<int> cn(26, 0);
    for (auto i: a) {
        an[i - 'a']++;
    }
    for (auto i: b) {
        bn[i - 'a']++;
    }
    int maxa= inff;
    for (int i = 0; i < 26; i++) {
        if (bn[i] > an[i]) {
            cout << 0 << endl;
            return;
        }
        maxa = max(maxa,bn[i]);
        cn[i] = bn[i];
    }
    bool flag = true;
    for (int i = 0; i < 26; i++){
        if(bn[i]){
            if(bn[i]!=maxa)flag= false;
        }

    }
    if(flag){
        int maxa= inf;
        for (int i = 0; i < 26; i++){
            if(bn[i]){
                maxa =max({0ll,min(maxa, an[i] - bn[i] + 1)});
            }
        }
        cout<<maxa<<endl;
        return;

    }

    int len = 1;
    while (1){
        for (int i = 0; i < 26; i++) {
            if ((bn[i]/2+bn[i]%2)+cn[i] > an[i]) {
                cout << len << endl;
                return;
            }
            cn[i] += (bn[i]/2+bn[i]%2);
        }
        len++;
    }
//    cout<<len<<endl;


}

#undef int


int main() {
    IOS
    int n;
    cin >> n;
//    n = 1;
    while (n--) {
        solve();
    }

}