#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef double lf;
typedef pair<int,int> pii;

const int A = 26;
const int INF = (int) 1e9;

int solve()
{
	string t, p;
	cin >> t >> p;

	vector< int > ft( A ), fp( A );
	for( char c : t )
		++ft[c-'a'];

	for( char c : p )
		++fp[c-'a'];

	const int n = (int) p.size();

	int ans = 0;
	for( int g = n; g; --g )
	{
		int mn = INF;
		for( int i = 0; i < A; ++ i )
		{
			if( fp[i] )
			{
				const int remainder = fp[i] % g;
				if( remainder == 0 || remainder == g - 1 )
				{
					const int cn = ( fp[i] + g - 1 ) / g;
					const int free = ft[i] - fp[i];

					if( free < 0 ) mn = -1;
					else mn = min( mn, free / cn );
				}
				else
					mn = -1;
			}
		}
		ans = max( ans, 1 + mn );
	}
	return ans;
}

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

	int t;
	cin >> t;
	while( t-- )
		cout << solve() << '\n';
	return 0;
}