题目描述

Jodie 慢慢地步入实验室，跟随在她身旁的灵体 Aiden 似乎有点不高兴，但还是形影不离地跟随着 Jodie。

今天 Jodie 要进行的实验在一个很大很大的圆环上面，圆环上有 $L$ 个格子，每个格子上都显示着一个小写英文字母，Jodie 从任意格子开始当她离开一个格子的时候那个格子的字母就会改变，这个改变是随机的，没有人知道会变成什么。Jodie 在这个环上不回头顺时针地走，每进入一个格子就会在本子上写下这个格子当前显示的字母。由于 Jodie 不能回头而且不知道这个圆环上有多少个格子，她并不知道自己什么时候会走到重复的点，所以她让 Aiden 在她下一步走进重复格子的时候提醒一下。但可能他们闹了矛盾，Aiden 发了脾气，决定在 Jodie 走了 $K$（$K \geq 0$）步重复的格子之后才告诉她。Jodie 进行了两次实验，记录了两次走的路径。第二次实验再进去之前，每个格子所显示的字母会被重设为第一次实验开始前的样子。Jodie 发现了 Aiden 的恶作剧，她只能把可能的最大的 $L$ 告诉实验人员。

为了帮助你更好的理解题目，请仔细分析一下例子：

假设 $L = 4$，$K = 1$

第一次实验开始前每个格子显示的字母如下图：

Jodie 从显示字母为 a 的格子开始走，Aiden 在她走了 $K$ 步重复的格子之后告诉她停止，所以 Jodie 一共走了 $5$ 步，每走一步，格子的变化如下（箭头指着 Jodie 所在的格子）：

Jodie 的第二次实验从显示字母为 c 的格子开始走，每走一步格子的变化如下（箭头指着 Jodie 所在的格子）：

Jodie 两次实验记录的路径分别为：

abcdx

cdabz

现在给出 Jodie 记录的两次路径的长度 $N$，以及 Jodie 所写的内容，但是并不知道 $K$ 是多少，希望你能帮忙求出一个最大的可能的 $L$。

输入格式

第一行：包含一个整数 $N$。

第二行：包含一个长度为 $N$ 的字符串，字符串中只包含小写字母。

第三行：包含一个长度为 $N$ 的字符串，字符串中只包含小写字母。

输出格式

输出答案只包含一个数字 $L$，表示圆环最大可能有的格子数。

5
abcdx
cdabz

4

4
abcd
cdab

4

提示

对于 $20\%$ 的数据，$1 \leq N \leq 5,000$

对于 $50\%$ 的数据，$1 \leq N \leq 600,000$

对于 $100\%$ 的数据，$1 \leq N \leq 2,000,000$