题目描述

已知一个仅由小写英文字母构成的字符串 $s$。

每次操作时，你可以任意选择 $s$ 中的一个字符，并将它修改为任意小写英文字母。

你可以按任意顺序对其进行不超过 $k$ 次操作，以最小化 $s$ 的严格循环节的长度。当然，不进行操作也是可以的。

请输出在进行完所有操作后，最小的可能的 $s$ 的严格循环节的长度。

一个字符串 $t$ 被称为 $s$ 的严格循环节，当且仅当 $s$ 可以通过将 $t$ 重复若干次来构造。

例如：mai 是 maimai 的严格循环节，dx 是 dx 的严格循环节。但 ov 不是 ovo 的严格循环节。

输入格式

第一行一个非负整数 $k$。

第二行一个字符串 $s$，仅包含小写英文字母。

输出格式

一行一个整数，表示答案。

1
test

4

3
test

1

3
apollo

3

提示

【样例解释 #1】

可以证明：最多进行一次操作的情况下，严格循环节长度至少为 $4$。

【样例解释 #2】

可以通过 $3$ 次操作，将 test 修改为 ssss，严格循环节长度为 $1$。

【数据范围】

本题采用捆绑测试。

• Subtask 0（17 pts）：$k = 0$，$|s| \leq 6$。
• Subtask 1（14 pts）：$k = 1$，$|s| \leq 20$。
• Subtask 2（16 pts）：$k = 1$，$|s| \leq 500$。
• Subtask 3（32 pts）：$k < |s| \leq 10^5$。
• Subtask 4（21 pts）： 无特殊限制。

对于所有测试数据，保证 $0 \leq k < |s| \leq 10^6$，$s$ 中仅包含小写英文字母。

2024.7.28：新增了一组 Hack 数据。