#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

	while (t--) {
		string S, T;
		cin >> S >> T;

		vector<int> cnt(26);
		for (char c : S) cnt[c - 'a']++;

		bool flag = true;
		for (char c : T) {
			if (cnt[c - 'a'] == 0) {
				flag = false;
				break;
			}
			cnt[c - 'a']--;
		}

		if (!flag) {
			cout << 0 << '\n';
		}
		else {
			vector<int> d(26);
			for (char c : T) d[c - 'a']++;

			int mn = 1e9;
			for (int x : d) if (x) mn = min(mn, x);

			int ans = 1;
			for (int k = 1; k <= mn; k++) {
				bool flag = true;
				for (int x : d) if (x) {
					if (x / k < x % k) flag = false;
				}
				if (!flag) continue;

				int s = 1e9;
				for (int i = 0; i < 26; i++) if (d[i]) {
					int rp = (d[i] / k) - (d[i] / k - d[i] % k) / (k + 1);
					s = min(s, cnt[i] / rp);

					// if (k == 1) {
					// 	cout << (char)('a' + i) << ' ' << rp << "?\n";
					// }
				}
				ans = max(ans, s + 1);
			}
			cout << ans << '\n';
		}
	}
}