Advertisement

An electronic sign continuously scrolls one advertisement text repeated without end. The size L of the sign is the number of characters visible at one moment, so exactly L characters are shown at a time.

Let N be the length of the actual advertisement text. The advertiser repeats this length-N text forever and scrolls it across the sign. For example, if the text is aaba and L=6, the sign may show aabaaa at one moment, then abaaab one second later, then baaaba after that as the text shifts by one character.

You are given the length-L string visible when Sejun looked at the sign. Find the shortest possible length of an advertisement text that could produce this string.

The first line contains the size L of the sign. The second line contains the length-L string currently visible on the sign.

Print the minimum possible length of the advertisement text.

• 1 <= L <= 1,000,000
• The visible string consists only of lowercase English letters.