#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int INF = 1000*1000*1000;

int main()
{
    int T;
    cin >> T;
    for(int teszt = 0; teszt < T; teszt++){
        string a = "0", b = "0", tempa, tempb;
        cin >> tempa >> tempb;
        a = a + tempa;
        b = b + tempb;
        //dp_final[i][j] a legkisebb hossz elso i es j karakterrel
        //dp_temp[i][j] a legkisebb hossz elso i es j karakterrel ugy, hogy az utolso karakter zarojelezve van
        vector<vector<int>> dp_final(a.size(), vector<int>(b.size(), INF)), dp_temp(a.size(), vector<int>(b.size(), INF));
        dp_final[0][0] = 0;
        dp_temp[0][0] = 3;
        for(int i = 0; i < a.size(); i++){
            for(int j = 0; j < b.size(); j++){
                int minim = dp_temp[i][j];
                if(i > 0){
                    minim = min(minim, dp_temp[i-1][j]+1);
                    minim = min(minim, dp_final[i-1][j]+4);
                }
                if(j > 0){
                    minim = min(minim, dp_temp[i][j-1]+1);
                    minim = min(minim, dp_final[i][j-1]+4);
                }
                dp_temp[i][j] = minim;
                dp_final[i][j] = min(dp_final[i][j], minim);
                if(i > 0 && j > 0 && a[i] == b[j]){
                    dp_final[i][j] = min(dp_final[i][j], dp_final[i-1][j-1] + 1);
                }
            }
        }
        cout << dp_final[a.size()-1][b.size()-1] << endl;
    }
    return 0;
}