Problem Statement

Shik's job is very boring. At day $0$, his boss gives him a string $S_0$ of length $N$ which consists of only lowercase English letters. In the $i$-th day after day $0$, Shik's job is to copy the string $S_{i-1}$ to a string $S_i$. We denote the $j$-th letter of $S_i$ as $S_i[j]$.

Shik is inexperienced in this job. In each day, when he is copying letters one by one from the first letter to the last letter, he would make mistakes. That is, he sometimes accidentally writes down the same letter that he wrote previously instead of the correct one. More specifically, $S_i[j]$ is equal to either $S_{i-1}[j]$ or $S_{i}[j-1]$. (Note that $S_i[1]$ always equals to $S_{i-1}[1]$.)

You are given the string $S_0$ and another string $T$. Please determine the smallest integer $i$ such that $S_i$ could be equal to $T$. If no such $i$ exists, please print -1.

Constraints

• $1 \leq N \leq 1,000,000$
• The lengths of $S_0$ and $T$ are both $N$.
• Both $S_0$ and $T$ consist of lowercase English letters.

Sample Input 1Copy

5
abcde
aaacc

Sample Output 1Copy

2

$S_0$ = abcde, $S_1$ = aaccc and $S_2$ = aaacc is a possible sequence such that $S_2 = T$.

Sample Input 2Copy

5
abcde
abcde

Sample Output 2Copy

0

Sample Input 3Copy

4
acaa
aaca

Sample Output 3Copy

2

Sample Input 4Copy

5
abcde
bbbbb

Sample Output 4Copy

-1