Edit Distance

In this problem, you are given two strings A and B. Your task is to compute the minimum number of operations required to convert A into B using only three allowed operations: insertion, deletion, and replacement of a single character.

The solution uses a dynamic programming approach. In particular, the recurrence used is given by:

[ dp[i][j] = \begin{cases} j, & \text{if } i = 0,\ i, & \text{if } j = 0,\ dp[i-1][j-1], & \text{if } A[i-1] = B[j-1],\ 1 + \min{ dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1] }, & \text{otherwise.} \end{cases} ]

You are required to read input from standard input (stdin) and write your output to standard output (stdout).

inputFormat

The first line of input contains a single integer T, representing the number of test cases. Each test case consists of two subsequent lines: the first line is string A and the second line is string B.

outputFormat

For each test case, output a single integer on a new line indicating the minimum number of operations required to convert string A into string B.## sample

3
horse
ros
intention
execution
abc
yabc

3
5
1