题目描述

一家无线电台需要向多位接收者发送一条信息。为了确保所有听众都能接收到，该信息在一个连续的循环中被一遍又一遍地播放。

你将得到其中一位接收者收到的一段字符序列。已知该序列的长度至少与原信息的长度一样长。

你的任务是编写一个程序，提取出电台发送的原信息。更形式化地说，你的程序需要找到输入序列 $S$ 的最短子序列 $S^{\prime}$，使得 $S$ 本身又是（足够长的）重复序列 $S^{\prime}+S^{\prime}+\cdot\cdot\cdot+S^{\prime}$ 的子串。

输入格式

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

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

输出格式

程序应向标准输出写入一行，包含一个整数：信息 $S^{\prime}$ 的长度 $L^{\prime}$。请注意，$L^{\prime}$ 必须是尽可能小的值。

8
cabcabca

3

提示

样例输入输出 1 解释

对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabcabc}$，读入的 $\texttt{cabcabca}$，是它的子串。

规模与约定

对于全部的测试点，保证 $1\le L \le 10^6$。