[Baltic2009]Radio Transmission

给定一个长度为 $L$ 的小写字母字符串 $s$。设字符串 $T$ 不断与自身连接，形成无限周期串 $TTT\cdots$。已知 $s$ 是该无限周期串的一个连续子串，其中 $s$ 不一定从某个 $T$ 的开头开始，且不要求 $|T|$ 整除 $L$。

求满足条件的字符串 $T$ 的最短长度。

输入格式

第一行输入一个整数 $L$，表示字符串的长度。

第二行输入一个长度为 $L$、仅由小写英文字母组成的字符串 $s$。

输出格式

输出一个整数，表示字符串 $T$ 的最短长度。

样例输入

8
cabcabca

样例输出

3

样例解释

字符串 abc 不断与自身连接可形成无限周期串 abcabcabc...，而输入的字符串 cabcabca 是它的一个连续子串，因此最短长度为 $3$。

数据范围

• $1\le L\le 10^6$；
• 字符串 $s$ 的长度为 $L$，且仅由小写英文字母组成。

来源与许可

本题为 Baltic 2009 试题「Radio Transmission」，题面与测试数据整理自 BZOJ。

样例 1

输入

8
cabcabca

输出

3