#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;

		int m = T.size();
		vector<int> F(m);
		for (int i = 1, p = 0; i < m; i++) {
			while (p && T[p] != T[i]) p = F[p - 1];
			if (T[p] == T[i]) F[i] = ++p;
		}

		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 (int i = 0; i < m - F[m - 1]; i++) {
				d[T[i] - 'a']++;
			}

			int ans = 1e9;
			for (int i = 0; i < 26; i++) {
				if (d[i]) ans = min(ans, cnt[i] / d[i]);
			}
			cout << ans + 1 << '\n';
		}
	}
}