题目描述

Shikk 的工作是复制。有一天，Shikk 从他的上司那里拿到了一个由小写英文字母组成的长度为 $N$ 的字符串 $S_{0}$（假设这天是第 $0$ 天）。这之后第 $i$ 天的工作是把 $S_{i-1}$ 复制到 $S_{i}$。下文中的 $S_{i}[j]$ 表示字符串 $S_{i}$ 的第 $j$ 个字母。

Shikk 还不怎么习惯这个工作。每天，当 Shikk 从第一个字母开始按顺序复制字符串时，他有可能会写下和刚刚写下的字母相同的字母，而不是本来应该写下的字母。也就是说，$S_{i}[j]$ 要么与 $S_{i-1}[j]$ 相同，要么与 $S_{i}[j-1]$ 相同。（特别地，字符串开头的字母不可能出错。也就是说，$S_{i}[1]$ 必然与 $S_{i-1}[1]$ 相同。）

输入两个字符串 $S_{0}$ 和 $T$，请求出使得 $S_{i}$ 有可能与 $T$ 相同的最小的整数 $i$。如果这样的 $i$ 不存在，请输出 $-1$。

样例解释

样例 1 解释

一种可能的最佳方案：$S_{0}= \texttt{abcde}$，$S_{1} = \texttt{aaccc}$，$S_{2} = \texttt{aaacc}$。

输入格式

输入的第一行仅一个整数，即字符串长度 $N$；

第二行仅一个由小写英文字母组成的字符串，即 $S_{0}$；

第三行仅一个由小写英文字母组成的字符串，即 $T$。

样例 1

输入

5
abcde
aaacc

输出

2

样例 2

输入

5
abcde
abcde

输出

0

样例 3

输入

4
acaa
aaca

输出

2

样例 4

输入

5
abcde
bbbbb

输出

-1

说明/提示

• $1\le N\le 10 ^ 6$；
• $S_{0}$ 和 $T$ 的长度都等于 $N$；
• $S_{0}$ 和 $T$ 均只由小写英文字母组成。