You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：2014 年湖北省队互测 Week2

「Madoka，不要相信 QB！」伴随着 Homura 的失望地喊叫，Madoka 与 QB 签订了契约。

这是 Modoka 的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次 Madoka 不再与 QB 签订契约，Homura 决定在刚到学校的第一天就解决 QB。然而，QB 也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的 Homura 是不会放弃的——她决定消灭所有可能是 QB 的东西。现在，她已感受到附近的状态，并且把它转化为一个长度为 $n$ 的字符串交给了学 OI 的你。

现在你从她的话中知道，所有形似于 $A+B+A$ 的字串都是 QB 或它的替身，且 $|A|\ge k,|B|\ge 1$ （位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），然后你必须尽快告诉 Homura 这个答案——QB 以及它的替身的数量。

注：对于一个字符串 $S$，$|S|$ 表示 $S$ 的长度。

输入格式

第一行一个字符串 $S$，第二行一个数 $k$。

输出格式

仅一行一个数 $\text{ans}$，表示 QB 以及它的替身的数量。

样例 1

aaaaa
1

6

abcabcabc
2

8

数据范围与提示

对于全部数据，$1\le |S|\le 1.5\times 10^4,1\le k\le 100$，且字符集为所有小写字母。