#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int T, cnt[26], ls, lt, c[26], w[26], all[26], cntt[26];
char s[maxn], t[maxn], tt[maxn];
int main() {
    for(scanf("%d", &T); T --; ) {
        scanf("%s%s", s + 1, t + 1);
        for(int i = 0; i < 26; ++ i)
            cnt[i] = all[i] = 0;
        ls = strlen(s + 1);
        lt = strlen(t + 1);
        for(int i = 1; i <= ls; ++ i)
            ++ all[s[i] - 'a'];
        for(int i = 1; i <= lt; ++ i)
            ++ cnt[t[i] - 'a'];
        int ansp = 1, ansl = lt;
        for(int len = 1; len <= lt; ++ len) {
            int per = lt / len, ex = lt % len;
            // period = per
            // lt = len * per + ex
            int totc = 0, more = 0;
            for(int i = 0; i < 26; ++ i) {
                c[i] = cnt[i] / per;
                w[i] = cnt[i] % per;
                totc += c[i];
                more += w[i];
            }
            if(more > ex)
                continue;
            for(int i = 0; i < 26 && more < ex; ++ i) {
                // every len has c[i], i
                while(more < ex && c[i]) {
                    c[i] -= 1;
                    w[i] += per;
                    more += per;
                }
                if(c[i] < w[i]) {
                    more = ex + 1;
                    break;
                }
            }
            if(more == ex) {
                ansp = per;
                ansl = len;
                break;
            }
        }
// cerr << "ansp = " << ansp << " ansl = " << ansl << endl;
        int ex = lt % ansl, p1 = 1, p2 = ex + 1;
        for(int i = 0; i < 26; ++ i) {
// cerr << w[i] << " " << c[i] << endl;
            c[i] -= w[i];
            while(w[i] --)
                tt[p1 ++] = i + 'a';
            while(c[i] --)
                tt[p2 ++] = i + 'a';
        }
        assert(p1 == ex + 1 && p2 == ansl + 1);
        // printf("%s\n", tt + 1);
        for(int i = 0; i < 26; ++ i)
            cntt[i] = 0;
        for(int i = 1; i <= ansl; ++ i)
            ++ cntt[tt[i] - 'a'];
        int totp = 1e9;
        for(int i = 0; i < 26; ++ i) {
            if(cntt[i]) {
                totp = min(totp, all[i] / cntt[i]);
            }
        }
        for(int i = 0; i < 26; ++ i) {
            all[i] -= cntt[i] * totp;
        }
        int ed = 0;
        for(int i = 1; i <= ansl; ++ i) {
            if(all[tt[i] - 'a'])
                -- all[tt[i] - 'a'];
            else {
                ed = i - 1;
                break;
            }
        }
// cerr << ansp << " " << ex << " " << totp << " " << ed << endl;
        int ans = max(0, (totp + (ex > 0 && ed >= ex)) - (ansp + (!!ex)) + 1);
        printf("%d\n", ans);
    }
}