import java.io.BufferedReader;
import java.io.InputStreamReader;

public class EditDistance {

	static char str1[], str2[];
	static int l1, l2;
	static int dp[][];

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		while (n-- > 0) {
			str1 = br.readLine().toCharArray();
			str2 = br.readLine().toCharArray();

			l1 = str1.length;
			l2 = str2.length;
			dp = new int[str1.length][str2.length];

			System.out.println(solve(0, 0));
		}
	}

	public static int solve(int i, int j) {
		if (i == l1) return (l2-j);
		if (j == l2) return (l1-i);
		if (dp[i][j] != 0)
			return dp[i][j];
		if (str1[i] == str2[j])
			return dp[i][j] = solve(i + 1, j + 1);
		return dp[i][j] = 1 + Math.min(Math.min(solve(i + 1, j), solve(i, j + 1)), solve(i + 1, j + 1));
	}
}