Hide

Problem O
Kínahvísl

Languages en is
/problems/kinahvisl/file/statement/en/img-0001.jpg
Image from pxfuel.com

Bartosz and his friends are playing a whispering game at their preschool.

The whispering games plays out with $N$ people sitting in a circle. Some particular person (lets number them $1$) thinks of a word and whispers it to the person on their left, person $2$. Person $2$ then whispers the word to the person on their left, person $3$. This continues until the person to the right of person $1$, let’s number them $N$, has a word whispered to them. At that point person $N$ announces out loud what they heard and person $1$ tells everyone what word they thought of in the beginning.

In this preschool all the kids hear the word whispered to them correctly, aside from a single letter, which gets changed.

Input

The first line of the input is the word person $1$ thought of, referred to as the initial word. On the second line is the word that person $N$ heard, referred to as the final word. The initial and final words are the same length. Only English lower case letters are used.

Úttak

One line containing the minimum possible value of $N$. That is to say, the lowest number of kids that would be needed for the initial word to turn into the final word by playing the whispering game.

Scoring

Group

Points

Constraints

1

10

The initial and final words are equal

2

20

The length of the initial and final words are both $\leq 100$

3

70

The length of the initial and final words are both $\leq 10^6$

Sample Input 1 Sample Output 1
tommi
dommi
2
Sample Input 2 Sample Output 2
pogger
pepega
6