#include<bits/stdc++.h>

std::vector<int> kmp(std::string& str) {
    int n = str.size();
    std::vector<int> v(1 + n);

    v[0] = -1;
    v[1] = 0;

    for (int i = 1; i <= n; i++) {
        v[i] = v[i - 1] + 1;
        while (v[i] > 0 && str[i - 1] != str[v[i] - 1])
            v[i] = v[v[i] - 1] + 1;
    }

    return v;
}

std::string xyxyx(std::vector<int> t) {
    std::string x, y;

    for (int i = 0; i < 26; i++) {
        if (t[i] == 1) return "";

        if (t[i] % 2 == 1) {
            x.push_back(i + 'a');
            t[i] -= 3;
        }

        while (t[i] - 6 >= 0) {
            x.push_back(i + 'a');
            x.push_back(i + 'a');
            t[i] -= 6;
        }

        while (t[i] - 2 >= 0) {
            y.push_back(i + 'a');
            t[i] -= 2;
        }
    }

    return x + y + x + y + x;
}

std::string xyx(std::vector<int> t) {
    std::string x, y;

    for (int i = 0; i < 26; i++) {
        while (t[i] - 2 >= 0) {
            x.push_back(i + 'a');
            t[i] -= 2;
        }

        if (t[i] > 0)
            y.push_back(i + 'a');
    }

    return x + y + x;
}

int get_ans(std::string& a, std::string b) {

    std::vector<int> fr_a(26);
    for (int i = 0; i < a.size(); i++)
        fr_a[a[i] - 'a']++;
    
    auto kmp_b = kmp(b);

    int longest = 0, res = 0;
    
    for (int i = 0; i < a.size(); i++) {
        int best = -1;
        int chosen = -1;

        for (int j = 0; j < 26; j++) {
            if (fr_a[j] > 0) {
                int len = longest + 1;
                if (len > b.size()) {
                    len = kmp_b[b.size()] + 1;
                }
                while (len > 0 && j + 'a' != b[len - 1])
                    len = kmp_b[len - 1] + 1;

                if (len > best) {
                    best = len;
                    chosen = j;
                }
            }
        }

        if (best == b.size())
            res++;

        longest = best;
        fr_a[chosen]--;
    }

    return res;
}

void solve_test() {
    std::string a, b;
    int nb;
    std::cin >> a >> b;

    std::vector<int> fr_b(26);

    for (int i = 0; i < b.size(); i++)
        fr_b[b[i] - 'a']++;

    int res = 0;

    std::string case_a = xyxyx(fr_b);
    if (!case_a.empty())
        res = std::max(res, get_ans(a, case_a));
    res = std::max(res, get_ans(a, xyx(fr_b)));

    std::cout << res << "\n";
}

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    int t;
    std::cin >> t;

    while (t--) solve_test();

    return 0;
}