#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>fail(m + 1);
        fail[0] = -1;
        for(int i=0;i<m;i++){
            int j = fail[i];
            while(j != -1 && t[i] != t[j]) j = fail[j];
            fail[i+1] = j + 1;
        }
        int ans = 0;
        {
            vector<int>freq(26);
            for(char ch : s) freq[ch - 'a']++;
            int x = 0;
            while(true){
                int c = t[x] - 'a';
                if(!freq[c]) break;
                freq[c]--;
                x++;
                if(x == m) ans++, x = fail[x]; 
            }
        }
        {
            vector<int>fs(26), ft(26);
            for(char ch : t) ft[ch - 'a']++;
            lint b1 = 1, b2 = 1;
            for(int i=0;i<m;i++) b1 = b1 * base1 % mod;
            for(int i=0;i<m;i++) b2 = b2 * base2 % mod;
            map<pair<lint, lint>, int>hash_freq;
            int cur = 0;
            for(int i=0;i<26;i++) if(fs[i] == ft[i]) cur++;
            lint hash1 = 0, hash2 = 0;
            for(int i=0;i<m;i++){
                int c = s[i] - 'a';
                if(fs[c] == ft[c]) cur--;
                fs[c]++;
                if(fs[c] == ft[c]) cur++;
                hash1 = hash1 * base1 + c + 1;
                hash2 = hash2 * base2 + c + 1;
            }
            if(cur == 26) hash_freq[{hash1, hash2}]++;
            for(int i=m;i<n;i++){
                int add = s[i] - 'a';
                int rem = s[i-m] - 'a';
                if(fs[rem] == ft[rem]) cur--;
                fs[rem]--;
                if(fs[rem] == ft[rem]) cur++;
                if(fs[add] == ft[add]) cur--;
                fs[add]++;
                if(fs[add] == ft[add]) cur++;
                hash1 = hash1 * base1 + add + 1;
                hash2 = hash2 * base2 + add + 1;
                hash1 = (hash1 - b1 * (rem + 1) % mod + mod) % mod;
                hash2 = (hash2 - b2 * (rem + 1) % mod + mod) % mod;
                if(cur == 26) hash_freq[{hash1, hash2}]++;
            }
            for(auto [p, x] : hash_freq) ans = max(ans, x);
        }
        cout<<ans<<"\n";
    }
    return 0;
}