#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define X first
#define Y second
#define umap unordered_map
using ll = long long;
using ull = unsigned long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, maxp = 31, inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-6;

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

	const int m = 26;
	vector<int> a(m), b(m);
	for (auto c : s) {
		a[c - 'a']++;
	}

	for (auto c : t) {
		b[c - 'a']++;
	}

	for (int i = 0; i < m; i++) {
		if (a[i] < b[i]) {
			cout << 0 << endl;
			return;
		}
	}

	auto check = [&](int k) {
		for (int i = 0; i < m; i++) {
			int p = b[i] / k, q = b[i] % k;
			if (p < q) return false;
		}

		return true;
	};

	int ans = 0;	

	for (int k = 1; k <= t.size(); k++) {
		int mn = inf;
		if (check(k)) {
			// cout << k << endl;
			for (int i = 0; i < m; i++) {
				if (!b[i]) continue;
				mn = min(mn, (a[i] - b[i]) / k);
				// cout << mn << endl;
			}

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

	cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}