#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

char s[N], t[N];

int n, m, nex[N], cnt[30], ct[30], ans;

void solve() {
    scanf("%s", s + 1); n = strlen(s + 1);
    scanf("%s", t + 1); m = strlen(t + 1);
    for (int i = 0; i < 26; i++) cnt[i] = ct[i] = 0;
    for (int i = 1; i <= n; i++) cnt[s[i] - 'a']++;
    for (int i = 1; i <= m; i++) {
        cnt[t[i] - 'a']--;
        if (cnt[t[i] - 'a'] < 0) {
            puts("0");
            return ;
        }
    }
    ans = 1;
    nex[1] = 0;
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && t[i] != t[j + 1]) j = nex[j];
        if (t[i] == t[j + 1]) j++;
        nex[i] = j;
    }
    for (int i = nex[m] + 1; i <= m; i++) ct[t[i] - 'a']++;
    int res = 1 << 30;
    for (int i = 0; i < 26; i++) if (ct[i]) res = min(res, cnt[i] / ct[i]);
    ans += res;
    printf("%d\n", ans);
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

/*
2
bajkaaall aal
abca cba

*/