#include<bits/stdc++.h>
using namespace std;
const int M=1005;
int tt,n,m;
string s,t;
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>tt;
	while(tt--){
		int cnt[M]={},cnt1[M]={},cnt2[M]={};
		string s1,s2;
		cin>>s>>t;
		for(int i=0;i<t.size();i++)cnt1[t[i]]++;
		for(int i=0;i<s.size();i++)cnt[s[i]]++;
		int mx=0;
		for(int i=0;i<t.size()-1;i++){
			s1=s1+t[i];
			s2=t[t.size()-1-i]+s2;
			if(s1==s2)mx=max(mx,i+1);
		}
//		printf("mx=%d\n",mx);
		for(int i=mx;i<t.size();i++)cnt2[t[i]]++;
		
		int mi=1e9;
		for(int i='a';i<='z';i++){
			if(cnt1[i]){
				if(cnt1[i]<=cnt[i])mi=min(mi,(cnt[i]-cnt1[i])/cnt2[i]+1);
				else mi=0;
			}
		}
		printf("%d\n",mi);
	}
	return 0;
}