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

using namespace std;

//Необходимо реализовать метод
//о алгоритме можно прочитать в источниках указанных в программе курса, или на странице курса в ЛМС
// или в презентациях к семинару.
int Wagner_Fischer_for_Damerau_Levenshtein(string &s, string &t)
{
    int res = 0;
    if (min(s.length(), t.length()) == 0)
    {
        return max(s.length(), t.length());
    }
    else
    if (s.length() > 1 &&
        t.length() > 1 &&
        s[s.length() - 1] == t[t.length() - 2] &&
        s[s.length() - 2] == t[t.length() - 1])
    {
        if (s[s.length() - 1] != t[t.length() - 1])
        {
            res = 1;
        }
        string s_1 = s.substr(0, s.length() - 1);
        string s_2 = s.substr(0, s.length() - 2);
        string t_1 = t.substr(0, t.length() - 1);
        string t_2 = t.substr(0, t.length() - 2);
        return min(min(Wagner_Fischer_for_Damerau_Levenshtein(s_1, t) + 1,
                       Wagner_Fischer_for_Damerau_Levenshtein(s, t_1) + 1),
                   min(Wagner_Fischer_for_Damerau_Levenshtein(s_1, t_1) + res,
                       Wagner_Fischer_for_Damerau_Levenshtein(s_2, t_2) + 1));
    }
    else
    {
        if (s[s.length() - 1] != t[t.length() - 1])
        {
            res = 1;
        }
        string s_1 = s.substr(0, s.length() - 1);
        string t_1 = t.substr(0, t.length() - 1);
        return min(min(Wagner_Fischer_for_Damerau_Levenshtein(s_1, t) + 1,
                       Wagner_Fischer_for_Damerau_Levenshtein(s, t_1) + 1),
                       Wagner_Fischer_for_Damerau_Levenshtein(s_1, t_1) + res);
    }
}

//Не изменять метод 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_for_Damerau_Levenshtein(s, t) << (i == n - 1 ? "" : " ");
        }
        fout.close();
        fin.close();
    }
    return 0;
}