trip String

E: Round-trip String

story

This is the world where all human beings have become competition programmers. In this world, there are many customs that you cannot think of in the present age. One of them is the custom of sending a character string when expressing gratitude to parents, especially mothers. There are regional differences in what kind of character string is suitable for sending, but in the northern land of Hokkaido, the simplest possible character string is suitable as a gift. Also, the sending mother needs to answer to the child how beautiful the sent string is in return.

Now you are being consulted by the mother of one child. The mother got a nice string from her child, but she can't really measure how great it is. According to the custom of Hokkaido, the character string T to be sent to the mother is made by reciprocating a certain character string S. At this time, if S is the shortest possible string, it is a better string T. The mother rewards her child for her hard work, so she wants to find the shortest string that can make a T, but that's difficult. I want you to make full use of your programming ability to solve your mother's worries.

problem

From a string S of length 2 or more, generate a string T of length N according to the following rules. Here, let K be the string length of S, and T [i] represents the i-th character of the string T. Here, the first character of T is the 0th character.

T [i] = S [K -1 --| (i $\ bmod$ (2K -2)) --K + 1 |]

Given only T, there can be multiple strings that produce T. Output the smallest string length K_ {min} among those strings.

Input format

N T

Constraint

• 2 \ leq N = | T | \ leq 1,000,000
• String consists of lowercase letters only

Output format

Output the length K_ {min} of the shortest string S that produces T.

Input example 1

6 tabata

Output example 1

3

There are three possible possibilities: tabata, tabat, and tab, but the answer is 3 because tab is the shortest.

Input example 2

Four hcpc

Output example 2

3

Input example 3

60 aaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbb

Output example 3

12

Example

Input

6 tabata

Output

3

inputFormat

outputFormat

Output the smallest string length K_ {min} among those strings.

Input format

N T

Constraint

• 2 \ leq N = | T | \ leq 1,000,000
• String consists of lowercase letters only

Output format

Output the length K_ {min} of the shortest string S that produces T.

Input example 1

6 tabata

Output example 1

3

There are three possible possibilities: tabata, tabat, and tab, but the answer is 3 because tab is the shortest.

Input example 2

Four hcpc

Output example 2

3

Input example 3

60 aaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbbbaaaaaaaaaaabbbbbbbbbb

Output example 3

12

Example

Input

6 tabata

Output

3

样例

6
tabata

3