给定一个长度为 $n$ 的字符串 $s = s_1s_2 \dots s_n$，仅由小写英文字母组成。为方便起见，我们定义 $s[l,r] = s_l s_{l+1} \dots s_r$，即 $s$ 从下标 $l$ 到 $r$ 的子串。

给定一个整数 $k$，你对那些由 $k$ 个相同的字符串拼接而成的 $s$ 的子串很感兴趣。请找出这些子串中最长的长度。

形式化地，你需要找到一组区间 $\{[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]\}$，满足以下两个条件：

• 对于每个 $i$ ($1 \le i \le k$)，$1 \le l_i \le r_i \le n$；
• 对于每个 $i$ ($1 \le i < k$)，$r_i + 1 = l_{i+1}$，且 $s[l_i, r_i] = s[l_{i+1}, r_{i+1}]$。

你需要最大化 $r_k - l_1 + 1$。

输入格式

第一行包含两个整数 $n, k$ ($2 \le k \le n \le 10^6$)。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写英文字母组成。

输出格式

输出一个整数，表示答案。特别地，如果没有这样的子串，输出 0。

样例

样例输入 1

5 3
bacbc

样例输出 1

0

样例输入 2

7 2
ababbba

样例输出 2

4

说明

对于第二个样例，我们选择的区间集合是 $\{[1, 2], [3, 4]\}$。可以证明这是满足条件的最长子串。