// Source: https://usaco.guide/general/io

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

const int lim = 2000000000;

int main() {
	int t;cin >> t; 
    while(t--){
        string a , b; cin >> a >> b;
        int n = a.size() , m = b.size();
        vector<vector<int>> dp1(n+2 , vector<int>(m+2 , lim)) , dp2(n+2 , vector<int>(m+2 , lim));
        dp1[1][1] = 0;
        dp2[1][1] = 3;
        for(int i = 1; i < n+2; i++){
            for(int j = 1; j < m+2; j++){
                dp2[i][j] = min(min(min(dp1[i-1][j]+4 , dp1[i][j-1]+4) , min(dp2[i-1][j]+1 , dp2[i][j-1]+1)), dp2[i][j]);
                dp1[i][j] = min(dp2[i][j] , dp1[i][j]);
                if(i != 1 && j!=1 && a[i-2] == b[j-2]){
                    dp1[i][j] = min(dp1[i-1][j-1]+1 , dp1[i][j]);
                }
            }
        }
        cout << dp1.back().back() << "\n";
    }
}