Minimum Cost Transformation

You are given two strings \(S\) and \(T\). Your task is to compute the minimum cost to transform string \(S\) into string \(T\) using a sequence of operations. In one operation, you may:

• Insert a character (cost = 1)
• Delete a character (cost = 1)
• Replace a character (cost = 1)

Formally, if you denote by \(\text{dp}[i][j]\) the minimum cost to convert the first \(i\) characters of \(S\) to the first \(j\) characters of \(T\), then the recurrence is given by:

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

Your solution must read from standard input and write the result to standard output.

inputFormat

The input begins with an integer \(K\) denoting the number of test cases. Following this, for each test case, there are two lines:

1. The first line contains the string \(S\) (it may be empty).
2. The second line contains the string \(T\) (it may be empty).

outputFormat

For each test case, output on a new line the minimum cost to transform \(S\) into \(T\).

2
kitten
sitting
flaw
lawn

3
2