#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <string>
using namespace std;

int calcSameness(string &s, int len_s, string &t, int len_t)
{
    if (len_s == 0)
        return len_t;
    if (len_t == 0)
        return len_s;
    if (len_s > 0 && len_t > 0 && s[len_s] == t[len_t - 1] && s[len_s - 1] == t[len_t])
        return min(min(min(calcSameness(s, len_s - 1, t, len_t) + 1,
                           calcSameness(s, len_s, t, len_t - 1) + 1),
                           calcSameness(s, len_s - 2, t, len_t - 2) + 1),
                           calcSameness(s, len_s - 1, t, len_t - 1) + (s[len_s] == t[len_t] ? 0 : 1));
    return min(min(calcSameness(s, len_s - 1, t, len_t) + 1,
                   calcSameness(s, len_s, t, len_t - 1) + 1),
                   calcSameness(s, len_s - 1, t, len_t - 1) + (s[len_s] == t[len_t] ? 0 : 1));
}

//Необходимо реализовать метод
//о алгоритме можно прочитать в источниках указанных в программе курса, или на странице курса в ЛМС или в презентациях к семинару.
int Wagner_Fischer_for_Damerau_Levenshtein(string& s, string& t)
{
    return calcSameness(s, s.length() - 1, t, t.length() - 1);
}

//Не изменять метод 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;
}