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

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

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

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

    b.clear();
    std::string patt;
    for (int i = 0; i < 26; i++) {
        int half = fr_b[i] / 2;
        for (int j = 0; j < half; j++)
            b.push_back('a' + i);
    }
    patt = b;

    for (int i = 0; i < 26; i++) {
        if (fr_b[i] % 2 == 1)
            b.push_back(i + 'a');
    }

    b = b + patt;

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

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