Description

Xiao Z has studied dialectical materialism and learned that connections are universal. Looking at the strings on his scratch paper, he wants to explore the relationships between them.

Xiao Z believes that for two strings $a,b$, if each can delete no more than half of its own length of characters to become equal, then $a,b$ are said to have a relationship with distance $1$. If there exists another string $c$ that has a distance of $1$ with $a$ and a distance of $n$ with $b$, then $a,b$ are said to have a relationship with distance $n + 1$.

Now Xiao Z randomly selects two lowercase letter strings $a,b$ and wants to know the minimal relationship distance between them. Please help him.

Input Format

The first line contains a string $a$.

The second line contains a string $b$.

Output Format

The first line contains an integer indicating the minimal relationship distance between $a,b$.

abcdef
axcyd

1

a
b

2

abb
baa

2

Hint

For $30\%$ of the testdata, $a,b$ are composed of the same letter.

For $100\%$ of the testdata, $1 \leq |a|,|b| \leq 100$.

Translated by ChatGPT 5