Problem Description

Xiao Z has learned dialectical materialism and understands that connections are universal. Looking at the strings on his draft paper, he wants to explore their relationships.

Xiao Z believes that for two strings \(a\) and \(b\), if they can each delete no more than half of their own length and become equal, then \(a\) and \(b\) have a relationship with a distance of 1. If there exists another string \(c\) that has a distance of 1 with \(a\) and a distance of \(n\) with \(b\), then \(a\) and \(b\) have a relationship with a distance of \(n + 1\).

Now, Xiao Z has randomly selected two lowercase letter strings \(a\) and \(b\) and wants to know the minimum distance of their relationship. He hopes you can 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 representing the minimum distance of the relationship between \(a\) and \(b\).

Sample Input and Output

Sample Input #1

abcdef
axcyd

Sample Output #1

1

Sample Input #2

a
b

Sample Output #2

2

Sample Input #3

abb
baa

Sample Output #3

2

Notes

For 30% of the data, \(a\) and \(b\) are composed of the same letter.

For 100% of the data, \(1 \leq |a|, |b| \leq 100\).

见题面 Input 部分

见题面 Output 部分