### 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