Minimum Edit Distance Transformation

Given two strings s and t, determine the minimum number of operations required to transform s into t. In each operation, you may perform one of the following: insertion, deletion, or replacement of a character. The dynamic programming approach is based on the recurrence:

(dp[i][j] = \begin{cases} i, & \text{if } j = 0,\ j, & \text{if } i = 0,\ dp[i-1][j-1], & \text{if } s_i = t_j,\ 1 + \min(dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1]), & \text{otherwise.} \end{cases})

Your task is to implement this algorithm and output the result for each test case.

inputFormat

The first line of standard input contains an integer T (T > 2), the number of test cases. Each of the following T lines contains three space-separated tokens: an integer (which can be ignored), a string s, and a string t.

outputFormat

For each test case, output one line with a single integer representing the minimum edit distance between s and t.## sample

7
4 int tint
5 hello shell
3 abc def
8 distance editing
10  abc
6 kitten sitting
4 flaw lawn

1
2
3
5
3
3
2