Repeated Pattern

Hyunwook finds comfort in repeating patterns. He wants to make everything take a repeating form. He has decided to start by turning the text of every book he owns into a repeating form.

A string has a repeated pattern if it can be made by repeating the same string two or more times. For example, abdeabde has a repeated pattern because it can be made by repeating abde two or more times, while abcefabce does not have a repeated pattern because no way of appending the same string repeatedly can produce it.

Hyunwook wants to turn the text written in a book into a repeated pattern. The content of the original string is printed in the book, so it cannot be changed, but he can attach paper to the end to add content. However, adding too much text makes his arm hurt, so he will append at most K characters.

When the book's text is turned into a repeated pattern, the longer the pattern, the more satisfaction Hyunwook feels. Excessive change would look unnatural, though, so the pattern's length is at most N characters. Help Hyunwook compute how to make the longest pattern.

The first line gives the length of the string N (1 ≤ N ≤ 100,000) and the number of characters that can be appended K (0 ≤ K ≤ 100,000).

The second line gives a string S of length N consisting only of lowercase English letters.

Print the maximum length of a pattern of length at most N that can be produced by appending at most K characters to make S a repeated pattern. If it cannot be made into a repeated pattern, print 0.