#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++f)
    cerr << (f ? ", " : "") << *L++;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  const auto solve = [] {
    string S, T;
    cin >> S >> T;
    int A[26] = {}, B[26] = {};
    for (char c : S) A[c - 'a'] += 1;
    for (char c : T) B[c - 'a'] += 1;
    for (int j = 0; j < 26; j++) {
      if (A[j] < B[j]) {
        return 0;
      }
    }

    for (int j = 0; j < 26; j++) {
      A[j] -= B[j];
    }

    const auto cdiv = [](int a, int b) {
      return (a + b - 1) / b;
    };

    const int n = max(S.size(), T.size());
    int mx = 0;
    for (int k = 1; k <= n; k++) {
      int cur = 1e9;
      for (int j = 0; j < 26; j++) {
        int C = cdiv(B[j], k + 1);
        int D = B[j] - C * k;
        assert (D <= C);
        if (C == 0) continue;
        cur = min(cur, A[j] / C + 1);
      }
      mx = max(mx, cur);
    }

    return mx;
  };

  int tc;
  cin >> tc;
  while (tc--)
    cout << solve() << '\n';

  return 0;
}