#include <iostream>
#include <vector>
using namespace std;

string a, b;
int n, m, I, J, ans;
vector <vector<int>> dp(3e3, vector<int>(3e3, 1e9));
vector <vector<int>> mni(3e3, vector<int>(3e3, 0));
vector <vector<int>> mnj(3e3, vector<int>(3e3, 0));

void solve() {
    cin >> a >> b;
    n = a.size();
    m = b.size();
    a = "a" + a;
    b = "a" + b;
    ans = 1e9;
    dp[0][0] = n + m + 3;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            I = (dp[mni[i - 1][j]][mnj[i - 1][j]] < dp[mni[i][j - 1]][mnj[i][j - 1]] ? mni[i - 1][j] : mni[i][j - 1]);
            J = (dp[mni[i - 1][j]][mnj[i - 1][j]] < dp[mni[i][j - 1]][mnj[i][j - 1]] ? mnj[i - 1][j] : mnj[i][j - 1]);
            mni[i][j] = I;
            mnj[i][j] = J;
            if (a[i] != b[j]) continue;
            dp[i][j] = (a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] - 1 : dp[I][J] + 2);
            if (i == n && j == m) dp[i][j] -= 3;
            mni[i][j] = (dp[i][j] < dp[I][J] ? i : I);
            mnj[i][j] = (dp[i][j] < dp[I][J] ? j : J);
        }
    }
    cout << dp[mni[n][m]][mnj[n][m]] << endl;
}

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) solve();
}