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

using ll = long long;

constexpr int maxn = 1e6 + 10, inf = 1e9;

char s[maxn], t[maxn];
int a[26], b[26], n, m;

void solve() {
  for (int i = 0; i < 26; ++i) a[i] = b[i] = 0;
  scanf("%s%s", s + 1, t + 1);
  n = strlen(s + 1), m = strlen(t + 1);
  for (int i = 1; i <= n; ++i) ++a[s[i] - 'a'];
  for (int i = 1; i <= m; ++i) ++b[t[i] - 'a'];
  for (int i = 0; i < 26; ++i) a[i] -= b[i];
  for (int i = 0; i < 26; ++i) {
    if (a[i] < 0) return cout << 0 << '\n', 0;
  }
  int ans1 = inf, ans2 = inf;
  int g = 0;
  for (int i = 0; i < 26; ++i) g = __gcd(g, b[i]);
  for (int i = 0; i < 26; ++i) if (b[i]) ans1 = min(ans1, a[i] / (b[i] / g));
  for (int i = 0; i < 26; ++i) if (b[i]) ans2 = min(ans2, a[i] / (b[i] + 1 >> 1));
  cout << max(ans1, ans2) + 1 << '\n';
}

int main() {
  int t; cin >> t;
  while (t--) solve();
}

answer.code: In function ‘void solve()’:
answer.code:19:43: error: return-statement with a value, in function returning ‘void’ [-fpermissive]
   19 |     if (a[i] < 0) return cout << 0 << '\n', 0;
      |                          ~~~~~~~~~~~~~~~~~^~~
answer.code:13:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   13 |   scanf("%s%s", s + 1, t + 1);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~