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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  int tt;
  cin >> tt;
  while(tt--) {
    string s, t;
    cin >> s >> t;
    vi cs(26), ct(26);
    rep(i, 0, sz(s)) cs[s[i] - 'a']++;
    rep(i, 0, sz(t)) ct[t[i] - 'a']++;
    bool ok = true;
    rep(i, 0, 26) if (cs[i] < ct[i]) {
      ok = false;
    }
    if (!ok) {
      cout << 0 << '\n';
      continue;
    }
    int ans = 0;
    for (int period = 1; period <= sz(t); period++) {
      bool ok = true;
      int res = 1e9;
      rep(c, 0, 26) {
        if (ct[c] == 0) continue;
        int amt = (ct[c] + period - 1)/ period;
        if (amt * (period - 1) > ct[c]) {
          ok = false;
        }
        res = min(res, (cs[c] - ct[c])/amt);
      }
      if (ok)
        ans = max(ans, res);
    }
    cout << ans+1 << '\n';
  }
}