#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 2e6 + 5;
int T;
char t[N], s[N];
int cntt[26], cnts[26];
int main(){
    read(T);
    while(T--){
        scanf("%s %s", t + 1, s + 1);
        int n = strlen(t + 1);
        int m = strlen(s + 1);
        for(int i = 0; i < 26; i++) cntt[i] = cnts[i] = 0;
        for(int i = 1; i <= n; i++) cntt[t[i] - 'a']++;
        for(int i = 1; i <= m; i++) cnts[s[i] - 'a']++;
        int maxx = m;
        for(int i = 0; i < 26; i++){
            if(cnts[i] != 0){
                maxx = min(maxx, cnts[i]);
            }
        }
        int ok = 0;
        for(int i = 1; i <= maxx; i++){
            bool flag = 0;
            for(int j = 0; j < 26; j++){
                if(cnts[j] == 0) continue;
                if(cnts[j] % i > cnts[j] / i) flag = 1;
            }
            if(!flag) ok = i;
        }
        int ans = n;
        for(int j = 0; j < 26; j++){
            if(cnts[j] == 0) continue;
            if(cntt[j] < cnts[j]) ans = 0;
            else{
                cntt[j] -= cnts[j];
                ans = min(ans, 1 + cntt[j] / (cnts[j] / ok));
            }
        }
        printf("%d\n", ans);
    }
}