#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define INFLL (ll)0x3f3f3f3f3f3f3f3f
const int MOD = 1e9 + 7, SZ = 1e5 + 10;
void solve(){
    string s, t;
    cin >> s >> t;
    int frqS[26] = {}, frqT[26] = {};
    for(char i : s) frqS[i - 'a']++;
    for(char i : t) frqT[i - 'a']++;
    for(int i = 0; i < 26; i++){
        if(frqT[i] > frqS[i]){
            return cout << "0\n", void();
        }
    }
    string a = "", b = "";
    for(int i = 0; i < 26; i++){
        while(frqT[i] > 1){
            a += (char)('a' + i);
            frqT[i] -= 2;
        }
        if(frqT[i]) b += (char)('a' + i);
    }
    for(char i : a){
        frqS[i - 'a']--;
    }
    int frq[26] = {};
    for(char i : a) frq[i - 'a']++;
    for(char i : b) frq[i - 'a']++;
    int ans = INF;
    for(int i = 0; i < 26; i++){
        if(frq[i] == 0) continue;
        ans = min(ans, frqS[i] / frq[i]);
    }
    cout << ans << endl;
}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
// by me