#include<iostream>
using namespace std;
#include<vector>
#include<string>

void solve() {
	string s, t;
	cin >> s >> t;

	int n = t.size(), m = s.size();

	vector<int> a(26), b(26), ans(n + 1, 1e9);

	for (int i = 0; i < n; ++i) a[t[i] - 'a']++;
	for (int i = 0; i < m; ++i) b[s[i] - 'a']++;
	for (int i = 0; i < 26; ++i) {
		if (b[i] < a[i]) {
			cout << "0\n";
			return;
		}
		b[i] -= a[i];
	}

	int answer = 1;

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 26; ++j) {
			if (a[j] == 0) continue;
			if (a[j] % (i + 1) == 0) {
				ans[i] = min(ans[i], b[j] / (a[j] / (i + 1)));
			}
			else if (a[j] / (i + 1) + a[j] % (i + 1) >= i) {
				ans[i] = min(ans[i], b[j] / (a[j] / (i + 1) + 1));
			}
			else ans[i] = 0;
		}
		answer = max(answer, 1 + ans[i]);
	}

	cout << answer << "\n";
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	cin >> t;
	while (t--) solve();

	return 0;
}