String Computer

A string-processing computer called the X9091 transforms an input string into a target string. Its instruction set has only three transformation instructions, and each one changes the string currently held in memory:

• Delete the character at a given position.
• Insert a character at a given position.
• Change the character at a given position to a different character.

Each instruction is written as ZXdd, where Z is the operation code (D, I, or C), X is a character, and dd is a two-digit position. A program ends with the halt instruction E. Each instruction acts on the string exactly as it is at the moment the instruction runs.

For example, the string abcde can be transformed into bcgfe by the following program (positions are counted from 1):

     abcde
Da01 bcde    delete the 'a' at position 1
Cg03 bcge    change position 3 to 'g'
If04 bcgfe   insert 'f' at position 4
E    bcgfe   halt

This program uses three transformation instructions (the halt E is not counted), and no shorter program exists for this pair of strings.

Given the input string and the target string, find the minimum number of transformation instructions (delete, insert, or change) needed to turn the input string into the target string.

The input consists of several lines. Each line contains two strings separated by exactly one space: the input string followed by the target string. Each string has at most 20 lowercase letters. The input ends with a line containing a single #.

For each input line, output a single line containing the minimum number of transformation instructions (delete, insert, or change) required to transform the input string into the target string.