#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;

int ans; 
bool check(vector <int> t, vector <int> a, int skip, int ans) {
	for(int i = 0; i < 26; i++) {
		// max(c) a / (t + c) >= ans 
		// a[i] >= ans * (t + c) 
		// t + c <= a[i] / ans
		int c = a[i] / ans; 
		if(c < t[i]) return false; 
		skip -= c - t[i];
	} if(skip <= 0) return true; 
	return false; 
}
void calc(vector <int> t, vector <int> a, int skip) {
	while(check(t, a, skip, ans + 1)) ++ ans;  
}

void Main() {
	string s, t; cin >> s >> t;
	vector<int> a(26);
	vector<int> b(26);
	for(char c : s) ++ a[c - 'a'];
	for(char c : t) ++ b[c - 'a'];
	ans = 0; 
	for(int i = 0; i < 26; i++)
		if(a[i] < b[i]) { cout << 0 << '\n'; return; }
	for(int i = 0; i < 26; i++)
		a[i] -= b[i];
	int n = s.length(), m = t.length();
	// cout << n << ' ' << m << endl;
	for(int len = m; len; len --) {
		bool ok = 1; 
		int tim = (m - 1) / len + 1;
		int add = tim * len - m;
		int sum = 0; 
		vector <int> t(26), bonus(26);
		for(int i = 0; i < 26; i++) {
			t[i] = b[i] ? (b[i] - 1) / tim + 1 : 0; 
			bonus[i] = t[i] * tim - b[i];
			if(bonus[i] > t[i]) { ok = 0; break; }
			sum += bonus[i];
		}
		// cout << "FFF--------- " << len <<' ' << tim << ' ' << add <<' ' << sum << endl;
		if(ok && sum <= add && (add - sum) % tim == 0) {
			int skip = (add - sum) / tim; 
			calc(t, a, skip);
			// cout << "FF " << len << ' ' << ans << endl;
		}
	} cout << ans + 1 << '\n';
}
int main() {
	#ifdef zqj
	freopen("1.in","r",stdin);
	#endif
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	for(int i = 0;i < T;++i) {
		Main();

	}
}