题目描述

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”。

输入输出格式

输入格式

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

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

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

输出格式

仅一行一个整数，即题目描述中所求的整数$i$。如果这样的$i$不存在，请输出“-1”（不包含引号）。

样例解释

样例1解释

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

样例5~8分别与样例1~4相同。

输出样例2、6均应为0。

说明

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