String Distance and Transform Process

Time Limit: 1000 ms Memory Limit: 10000 KiB

Problem Description

String Distance is a non-negative integer that measures the distance between two strings. Here we give the definition. A transform list is a list of string, where each string, except for the last one, can be changed to the string followed by adding a character, deleting a character or replacing a character. The length of a transform list is the count of strings minus 1 (that is the count of operations to transform these two strings). The distance between two strings is the length of a transform list from one string to the other with the minimal length. You are to write a program to calculate the distance between two strings and give the corresponding transform list.

Input

Input consists a sequence of string pairs, each string pair consists two lines, each string occupies one line. The length of each string will be no more than 80.

Output

For each string pair, you should give an integer to indicate the distance between them at the first line.  

Sample Input

abcac
bcd
aaa
aabaaaa

Sample Output

3
4

Hint


Source