#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <string>

using namespace std;

///Необходимо реализовать метод
///о алгоритме можно прочитать в источниках указанных в программе курса, или на странице курса в ЛМС
/// или в презентациях к семинару.
int Wagner_Fischer(string &s, string &t)
{
    int d[s.length() + 3][t.length() + 3];

    for (int i = 0; i <= s.length() + 2; i++)
    {
        for (int j = 0; j <= t.length() + 2; j++)
        {
            d[i][j] = 0;
        }
    }

    for (int i = 0; i <= s.length() + 2; i++)
    {
        for (int j = 0; j <= t.length() + 2; j++)
        {
            d[i][0] = i;
            d[0][j] = j;
        }
    }

    int res = 0;

    for (int i = 1; i <= s.length(); i++)
    {
        for (int j = 1; j <= t.length(); j++)
        {
            if (s[i - 1] == t[j - 2] && s[i - 2] == t[j - 1] && i > 1 && j > 1)
            {
                if (s[i - 1] != t[j - 1])
                {
                    res = 1;
                }
                d[i][j] = min(
                        min(d[i - 1][j] + 1,
                            d[i][j - 1] + 1),
                        min(d[i - 1][j - 1] + res,
                            d[i - 2][j - 2] + 1));
            }
            else
            {
                if (s[i - 1] != t[j - 1])
                {
                    res = 1;
                }
                d[i][j] = min(
                        min(d[i - 1][j] + 1,
                            d[i][j - 1] + 1),
                        d[i - 1][j - 1] + res);
            }
        }
    }

    return d[s.length()][t.length()];
}

///Не изменять метод main без крайней необходимости
///ОБЯЗАТЕЛЬНО добавить в комментариях подробные пояснения и причины побудившие вас изменить код этого метода.
int main(int argc, const char *argv[])
{
    int n;
    fstream fin;
    fstream fout;
    fin.open("input.txt", ios::in);
    fout.open("output.txt", ios::out);
    if (fin.is_open())
    {
        string N;
        getline(fin, N);
        n = atoi(N.c_str());
        for (int i = 0; i < n; i++)
        {
            string s;
            string t;
            getline(fin, s);
            getline(fin, t);
            fout << Wagner_Fischer(s, t) << (i == n - 1 ? "" : " ");
        }
        fout.close();
        fin.close();
    }
    return 0;
}