#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;
    int g = 0;
    for (int i = 0; i < 26; i++) {
        if (bn[i]) {
            if (!g) {
                g = bn[i];
            } else {
                g = __gcd(g, bn[i]);
            }
        }
    }
    if (g != 1) {
        int ma = inf;
        for (int i = 0; i < 26; i++) {
            bn[i] /= g;
        }
        for (int i = 0; i < 26; i++) {
            if (bn[i]) {
                an[i] /= bn[i];
                ma = max(0ll, min(ma, an[i] - cn[i]/bn[i] + 1));
            }
        }
        cout << ma << 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();
    }

}