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

string a, b;
int n, m, Mn, ans;
vector <vector <int>> dp(3e3, vector <int>(3e3, 1e9));
vector <vector <int>> mn(3e3, vector <int>(3e3, 0));

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

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