#include "bits/stdc++.h"

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

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

void solve(int TC) {
	string s;
	string t;
	cin >> s >> t;

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

	vector<int> freqs(26), freqt(26);
	for (auto ch: s) {
		freqs[ch - 'a']++;
	}
	for (auto ch: t) {
		freqt[ch - 'a']++;
	}

	for (int i = 0; i < 26; i++) {
		freqs[i] -= freqt[i];
		if (freqs[i] < 0) {
			cout << "0\n";
			return;
		}
	}

	vector<vector<int>> d(26, vector<int>(m + 1, 1e9));
	for (int c = 0; c < 26; c++) {
		for (int i = 1; i <= freqt[c]; i++) {
			if (freqt[c] % i == 0) {
				d[c][freqt[c] / i + 1] = min(d[c][freqt[c] / i + 1], i);
			}
			d[c][freqt[c] / i] = min(d[c][freqt[c] / i], i);
		}
	}

	int ans = 0;

	for (int i = 1; i <= m; i++) {
		bool fail = false;

		for (int c = 0; c < 26; c++) {
			if (freqt[c] == 0) continue;

			if (d[c][i] == 1e9) {
				fail = true;
				break;
			}

		}
		if (fail) continue;

		int mn = 1e9;
		for (int c = 0; c < 26; c++) {
			if (freqt[c] > 0) {
				mn = min(mn, freqs[c] / d[c][i]);
			}
		}

		ans = max(ans, mn + 1);
	}

	cout << ans << "\n";
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}