#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        string a,b;
        cin >> a >> b;
        if(a.length() < b.length()) swap(a,b);
        int dp[a.length()+1][b.length()+1][2];
        dp[0][0][0]=0;
        dp[0][0][1]=3;
        for(int i = 1; i <= a.length(); i++){dp[i][0][1]=i+3; dp[i][0][0]=1e5;}
        for(int i = 1; i <= b.length(); i++){dp[0][i][1]=i+3; dp[0][i][0]=1e5;}
        for(int i = 1; i <= a.length(); i++){
            for(int j = 1; j <= b.length(); j++){
                if(a[i-1]==b[j-1]){
                    //cout << "ok";
                    dp[i][j][0]=min(dp[i-1][j-1][0], dp[i-1][j-1][1])+1;
                    dp[i][j][1]=dp[i-1][j-1][1]+2;
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][1]+1);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][1]+1);
                }else{

                    dp[i][j][0]=1e5;
                    dp[i][j][1]=dp[i-1][j-1][1]+2;
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][0]+5);
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][0]+4);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][0]+4);
                    dp[i][j][1]=min(dp[i][j][1], dp[i-1][j][1]+1);
                    dp[i][j][1]=min(dp[i][j][1], dp[i][j-1][1]+1);
                }
            //cout << dp[i][j][0] << " "<<dp[i][j][1] << "    :" << i << " " << j << endl;
            }//cout << endl;
        }
        cout << min(dp[a.length()][b.length()][0], dp[a.length()][b.length()][1]) << endl;
    }
}