Vinícius has an interesting typing machine. The machine accepts instructions consisting of a non-empty string $$$s$$$ and a positive integer $$$n$$$. For each such instruction, the machine prints $$$n$$$ characters: the $$$i$$$-th ($$$0$$$-based) printed character equals $$$s_r$$$, where $$$r$$$ is the remainder after dividing $$$i$$$ by the length of $$$s$$$ and $$$s_r$$$ denotes the $$$r$$$-th ($$$0$$$-based) character of $$$s$$$. For instance, with the sequence of instructions:
Vinícius is lazy, so he only gives strings of length at most $$$D$$$ to the machine in each instruction. Since he is very lazy, he also wants to use as few instructions as possible. Given a string $$$T$$$ and the integer $$$D$$$, help Vinícius find the minimum number of instructions he needs in order to print $$$T$$$ using the machine.
The input consists of a single line that contains a string $$$T$$$ of lowercase letters followed by the integer $$$D$$$ ($$$1 \leq D \leq |T| \leq 2 \times 10^5$$$), as described in the statement.
Output a single line with an integer indicating the minimum number of instructions Vinícius needs.
ababcdcxx 2
3
aaabbcd 1
4
abcabca 3
1
