import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;
import static java.lang.System.*;
import static java.lang.Integer.*;
import static java.lang.Double.*;
import static java.lang.Math.*;

public class EditDist
{

    public void run() throws Exception
    {
        Scanner file = new Scanner(new File("EditDistance.dat"));

        int times = file.nextInt();
        file.nextLine();

        for (int asdf = 0; asdf < times; asdf++)
        {
            String s1 = file.nextLine();
            String s2 = file.nextLine();
            int[][] dp = new int[s1.length()+1][s2.length()+1];
            for(int i = 0; i < dp.length-1; i++)
            {
                for(int j = 0; j < dp.length-1; j++)
                {
                    if(s1.substring(i, i+1).equals(s2.substring(j, j+1))) dp[i+1][j+1] =dp[i][j]; //Im confused here
                    else dp[i+1][j+1] = Math.min(dp[i][j]+1, Math.min(dp[i][j+1]+1, dp[i+1][j]+1));
                }
            }
            System.out.println(dp[s1.length()][s2.length()]);
            //Question : will the answer always be in the bottom right cell bc you are bringing it down right?
        }
    }

    public static void main(String[] args) throws Exception
    {

        new EditDist().run();
        //data
        /*
        4
        abcdefghijklmnopqrstuvxyz
        zyxvutsrqponmlkjihgfedcba
        Ral
        The Ral
        Steven
        Steven
        abcdefg
        abdcegg
        */
        //output              //correct output
        /*
        24                    24
        0                     4
        0                     0
        3                     3
        */
    }

}