Minimum Edit Distance Transformation

You are given two strings s1 and s2. Your task is to compute the minimum number of operations required to transform s1 into s2. The allowed operations are insertion, deletion, and substitution of a single character.

This problem is a classic example of dynamic programming. The recurrence relation for the edit distance 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 } s1[i-1]=s2[j-1] \\ 1+\min\{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]\},& \text{if } s1[i-1]\neq s2[j-1] \end{cases}\)

Input is read from standard input (stdin). Each test case consists of two lines representing the two strings. The end of input is signaled by a line containing END (which is not part of any test case). For each pair of strings, output the result in the format Case #X: Y, where X is the test case number (starting from 1) and Y is the minimum number of operations required.

inputFormat

The input is read from standard input and consists of multiple lines. Each test case is made up of two consecutive lines where the first line is the string s1 and the second line is the string s2. The input is terminated by a line containing END (which is not part of any test case).

outputFormat

For each test case, output one line in the format: Case #X: Y, where X is the test case number (starting from 1), and Y is the minimum number of operations required to transform s1 into s2. Each output line should be printed to standard output.

## sample

kitten
sitting
END

Case #1: 3

</p>