#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
typedef long long ll;
typedef pair<int,int> pii;
template<class T> void print(T & x){ cout << x; }
template<class T,class U> void print(pair<T,U> & p){cout << "("; print(p.first); cout << ", "; print(p.second); cout << ")"; }
template<class T> void print(vector<T> & v) {
  cout << "{";
  if (sz(v)) print(v[0]);
  for (int i = 1; i < sz(v); i++) cout << ", ", print(v[i]);
  cout << "}\n";
}


vector<int> calc(string& X){
  vector<int> cnt(26);
  for(char c : X)
    cnt[c-'a']++;
  return cnt;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int TC;
  cin >> TC;
  while(TC--){
    string T, S;
    cin >> S >> T;
    vector<int> t = calc(T);
    vector<int> s = calc(S);
    set<int> pos;
    for(int i=0; i<sz(T); i++){
      pos.insert(i+1);
    }
    for(int c=0; c<sz(t); c++){
      if(t[c] == 0)
        continue;
      set<int> newp;
      for(int x : pos){
        int perbin = t[c]/x;
        int lft = t[c]%x;
        if(lft <= perbin)
          newp.insert(x);
      }
      pos = newp;
    }
    int k = *(--pos.end());
    //cout << "k: " << k << endl;
    int res = sz(S);
    for(int c=0; c<sz(t); c++){
      if(t[c] == 0)
        continue;
      if(s[c] < t[c]){
        res = 0;
        continue;
      }
      s[c] -= t[c];
      int perbin = (t[c]+k) / (k+1);
      //cout << c << " left " << s[c] << " .. " << perbin << " " << k << endl;
      res = min(res, s[c]/perbin + 1);
    }
    cout << res << "\n";
  }
}