#include <bits/stdc++.h>

using namespace std;

#define iter(v) v.begin(), v.end()
#define SZ(v) int(v.size())
#define pb emplace_back
#define ff first
#define ss second

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#ifdef zisk
void debug(){cerr << "\n";}
template<class T, class ... U>
void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while(l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

void solve(){
	string S, T;
	cin >> S >> T;

	vector<int> cs(26), ct(26);
	for(char i : S) cs[i - 'a']++;
	for(char i : T) ct[i - 'a']++;
	
	for(int i = 0; i < 26; i++){
		if(cs[i] < ct[i]){
			cout << "0\n";
			return;
		}
	}

	vector<int> tmp;
	for(int k = 1; k <= SZ(T); k++)
		tmp.pb(SZ(T) / k);
	sort(iter(tmp));
	tmp.resize(unique(iter(tmp)) - tmp.begin());

	
	int ans = 0;
	for(int t : tmp){
	
		vector<int> use(26);
		bool ok = true;
		for(int i = 0; i < 26; i++){
			int cnt = ct[i];
			if(cnt == 0) continue;
			if((ll)(cnt % t) * (t + 1) > cnt){
				ok = false;
				break;
			}
			int b = (cnt / (t + 1) - (cnt % t)) / t * t + cnt % t;
			int a = (cnt - b) / t - b;
			assert(a * t + b * (t + 1) == cnt);
			use[i] = a + b;
		}
		if(!ok) continue;

		int cur = 1e9;
		for(int i = 0; i < 26; i++){
			if(use[i] == 0) continue;
			cur = min(cur, 1 + (cs[i] - ct[i]) / use[i]);
		}
		ans = max(ans, cur);
	}
	cout << ans << "\n";

}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	while(T--) solve();

}