Substring substitution P43134

Given two strings of the same length, composed only by lowercase letters, please compute the minimum amount of transformations needed to convert the first string into the second. A transformation is defined as selecting a contiguous substring s of the first string, choosing a lowercase letter c, and changing every character in s by c.

Input

Input consists of several cases, each with two strings s₁ and s₂ of the same length, between 1 and 50.

Output

For every case, print its number followed by the least amount of transformations needed to convert s₁ into s₂.