#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
typedef long long ll;
ll n;
char s1[N],s2[N];
int cnt1[30],cnt2[30];
int cntneed[30];

bool check(int c1[],int c2[]){
    for(int i=0;i<26;i++){
        if(c1[i]<c2[i]) return false;
        c1[i]-=c2[i];
    }
    return true;
}


void HuangGuangsheng(){
    scanf("%s",s1+1);
    scanf("%s",s2+1);
    int n1=strlen(s1+1),n2=strlen(s2+1);
    memset(cnt1,0,sizeof cnt1);
    memset(cnt2,0,sizeof cnt2);
    memset(cntneed,0,sizeof cntneed);
    for(int i=1;i<=n1;i++) cnt1[s1[i]-'a']++;
    for(int i=1;i<=n2;i++) cnt2[s2[i]-'a']++;
    for(int i=0;i<26;i++) cntneed[i]=(cnt2[i]+1)/2;
    int ans=0;
    if(check(cnt1,cnt2)) ans++;
    else{
        puts("0");
        return;
    }
    while(check(cnt1,cntneed)) ans++;
    printf("%d\n",ans);
}

int main(){
    int hgs;
    cin>>hgs;
    while(hgs--){
        HuangGuangsheng();
    }
}