#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int INF = 0x3fffffff;

array<int,26> readString(){
	array<int,26> ans;
	ans.fill(0);
	string s;
	cin >> s;
	for(char c:s){
		ans[c-'a']++;
	}
	return ans;
}

void solve(){
	auto s = readString();
	auto t = readString();
	array<set<int>,26> lts;
	for(int i=0;i<26;i++){
		for(int h=1;h<=t[i];h++){
			if(t[i]%h==0){
				if(t[i]!=h){
					lts[i].insert(t[i]/h-1);
				}
				lts[i].insert(t[i]/h);
			}else{
				lts[i].insert(t[i]/h);
			}
		}
	}
	int lt = INF;
	for(int i=0;i<26;i++){
		if(t[i]>0){
			lt = min(lt,t[i]);
		}
	}
	while(true){
		bool flag = true;
		for(int i=0;i<26;i++){
			if(lts[i].empty()) continue;
			if(!lts[i].count(lt)){
				flag = false;
				break;
			}
		}
		if(flag) break;
		lt--;
	}
	array<int,26> lc;
	for(int i=0;i<26;i++){
		if(t[i]%(lt+1)==0){
			lc[i] = t[i]/(lt+1);
		}else{
			lc[i] = (t[i]+lt)/(lt+1);
		}
	}
	int ans = INF;
	for(int i=0;i<26;i++){
		s[i] -= t[i];
		if(s[i]<0){
			cout << "0" << '\n';
			return;
		}
		if(lc[i]>0){
			s[i] /= lc[i];
			ans = min(ans,s[i]+1);
		}
	}
	cout << ans << '\n';
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int T;
	cin >> T;
	while(T--) solve();
	return 0;
}