#include <bits/stdc++.h>
 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 210, maxq = 1e5 ,  N = 1e5 +1 , lg = 20 , sq =1700   , inf = 1e18, maxk = 2022 , mod =998244353;
int s[maxn] , t[maxn] , x[maxn];

int sl(){
  int mn = inf ;
  rep(i , 0 ,25){ 
    if(x[i]==0)continue ; 
    mn = min(mn , s[i]/x[i]) ; 
  }
  return mn ; 
}

signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);   
  int z ;cin >> z ; 
  while(z--){
    string A , B;
    cin >> A >> B ;
    int ans =1  ;
    rep(i , 0 , 25)s[i] = t[i]= x[i] = 0 ;
    rep(i , 0 ,sz(A)-1)s[A[i]-'a']++;
    rep(i , 0 ,sz(B)-1)t[B[i]-'a']++;
    rep(i , 0 , 25){
      if(s[i] < t[i]){
        ans =0 ;
        break ;
      }
      s[i] -= t[i] ; 
    }
    if(ans == 0){
      cout << "0\n" ;
      continue ;
    }
    rep(i , 0 , 25)x[i] = (t[i]+1)/2 ;
    int mx = sl()  ;
    rep(i ,2 , sz(A)){
      bool ok = 0 ;
      rep(j , 0 ,25){
        x[j] = (t[j] + i) / (i+1) ;
        if(x[j]*i > t[j])ok = 1; 
      }
      if(ok == 1)continue ; 
      mx = max(mx , sl()); 
    }
    cout << 1+mx << "\n" ;
  }
}
/*
*/