import java.util.Scanner;

public class Main {

	private static Scanner s;
	static char[] str1;
	static char[] str2;
	static int sz1, sz2;
	static int[][] mem = new int[2001][2001];
	static int i, j;

	public static int dp(int i, int j) {
		if (i == sz1)
			return sz2 - j;
		if (j == sz2)
			return sz1 - i;
		if (mem[i][j] != -1)
			return mem[i][j];
		if (str1[i] == str2[j])
			return mem[i][j] = dp(i + 1, j + 1);

		int cho1 = dp(i + 1, j) + 1;
		int cho2 = dp(i, j + 1) + 1;
		int cho3 = dp(i + 1, j + 1) + 1;
		return mem[i][j] = Math.min(cho1, Math.min(cho2, cho3));

	}

	public static void main(String[] args) {
		s = new Scanner(System.in);

		int t = s.nextInt();
		while (t > 0) {
			for (i = 0; i <= 2000; i++)
				for (j = 0; j <= 2000; j++)
					mem[i][j] = -1;
			str1 = s.next().toCharArray();
			str2 = s.next().toCharArray();
			sz1 = str1.length;
			sz2 = str2.length;
			System.out.println(dp(0, 0));
			t--;
		}
	}
}