Problem C
Radio Transmission

A radio station needs to transmit a message to several recipients. To ensure all listeners get it, the message is played again and again in a continuous loop.

You’re given a sequence of characters recieved by one of the recipients. It is known that the sequence is at least as long as the message.

Your task is to write a program the extracts the message transmitted by the station. More formally, your program needs to find the shortest subsring $S^{\prime }$ of the input string $S$ such that $S$ in turn is a substring of the (sufficiently long) repetition $S^{\prime }+S^{\prime }+\dots +S^{\prime }$.

Input

The first line contains a single integer $1\le L\le 1000000$, the length of the string $S$. The second line contains exactly $L$ characters, the string $S$ itself. The sequence consists of lowercase letters a-z.

Output

The program should write one line to standard output containing a single integer: the length $L^{\prime }$ of the message $S^{\prime }$. Note that $L^{\prime }$ must be the smallest possible. If there are multiple smallest $L^{\prime }$, you may output any of them.

Explanation of Sample 1

The message could (among other options) be “abc”, “cab” or “abcabc”, but there is no possible message shorter than $3$ characters.

8
cabcabca

3