题目描述

给你一个下标从 0 开始的字符串 $word$ 和一个整数 $k$ 。

在每一秒，你必须执行以下操作：

• 移除 $word$ 的前 $k$ 个字符。
• 在 $word$ 的末尾添加 $k$ 个任意字符。

注意 添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行 两种 操作。

返回将 $word$ 恢复到其 初始 状态所需的 最短 时间（该时间必须大于零）。

输入格式

第一行一个字符串表示 $word$；

第二行一个正整数 $k$

输出格式

一行一个整数表示答案。

样例

示例 1：

abacaba
3

2

解释：

第 1 秒，移除 word 的前缀 "aba"，并在末尾添加 "bac" 。因此，word 变为 "cababac"。

第 2 秒，移除 word 的前缀 "cab"，并在末尾添加 "aba" 。因此，word 变为 "abacaba" 并恢复到始状态。

可以证明，2 秒是 word 恢复到其初始状态所需的最短时间。

示例 2：

abacaba
4

1

解释：

第 1 秒，移除 word 的前缀 "abac"，并在末尾添加 "caba" 。因此，word 变为 "abacaba" 并恢复到初始状态。

可以证明，1 秒是 word 恢复到其初始状态所需的最短时间。

示例 3：

abcbabcd
2

4

解释：

每一秒，我们都移除 word 的前 2 个字符，并在 word 末尾添加相同的字符。

4 秒后，word 变为 "abcbabcd" 并恢复到初始状态。

可以证明，4 秒是 word 恢复到其初始状态所需的最短时间。

数据范围与提示

• $1 <= word.length <= 10^6$
• $1 <= k <= word.length$
• $word$仅由小写英文字母组成。