Edit Distance Transformation

Given two strings ( s_1 ) and ( s_2 ), your task is to compute the minimum number of operations required to transform ( s_1 ) into ( s_2 ). The allowed operations are insertion, deletion, and substitution. The problem is defined by the recurrence: [ \text{dp}[i][j] = \begin{cases} j, & \text{if } i=0 \ i, & \text{if } j=0 \ \text{dp}[i-1][j-1], & \text{if } s_1[i-1] = s_2[j-1] \ 1+\min{\text{dp}[i][j-1],, \text{dp}[i-1][j],, \text{dp}[i-1][j-1]}, & \text{otherwise} \end{cases} ] Read the input from standard input and print the output to standard output.

inputFormat

The first line contains an integer ( T ), the number of test cases. Each of the following ( T ) lines contains two space-separated strings ( s_1 ) and ( s_2 ).

outputFormat

Output ( T ) lines, where each line contains a single integer representing the minimum number of operations required to transform ( s_1 ) into ( s_2 ) for that test case.## sample

2
kitten sitting
flaw lawn

3
2