一个无线电台需要向若干接收者发送一条消息。为了确保所有听众都能收到，该消息会被不断循环播放。

给你一个由其中一位接收者接收到的字符序列 $S$。已知该序列的长度至少与原消息一样长。

你的任务是编写一个程序来提取电台发送的消息。更正式地，你的程序需要找到输入序列 $S$ 的最短子串 $S'$，使得 $S$ 是（足够长的）重复序列 $S' + S' + \dots + S'$ 的子串。

输入格式

输入从标准输入读取。

第一行包含一个整数 $L$，表示序列 $S$ 的长度。

第二行恰好包含 $L$ 个字符，即序列 $S$ 本身。该序列由小写字母（a ... z）组成。

输出格式

程序应向标准输出写入一行，包含一个整数：消息 $S'$ 的长度 $L'$。注意 $L'$ 必须尽可能小。

样例

输入样例 1

8
cabcabca

输出样例 1

3

说明 1

消息可以是 abc、cab 或 abcabc，但不存在长度小于 3 的可能消息。

数据范围

$1 < L \le 1\,000\,000$。

注意，在可用的标准库中，字符串匹配函数（C 中的 strstr，C++ 中的 string::find，或 Pascal 中的 pos）在最坏情况下的时间复杂度为 $\Theta(nm)$，当在长度为 $m$ 的字符串中搜索长度为 $n$ 的子串时。