[EER2] 出言不逊

你出言不逊是！！

珂愛想出公开赛，但每次都被拒绝。 珂愛很生气，于是学会了出言不逊。 珂愛用一个字符串 $S$ 存储了她想说的话，但这句话太逊了。为了出言不逊，珂愛要对字符串进行操作。每次操作，珂愛可以选择一个字符 $c$，若 $c$ 在字符串 $S$ 中出现了 $x$ 次，则珂愛会将 $x$ 个字符 $c$ 补到 $S$ 的尾部。 珂愛认为，这个字符串长度至少为 $L$ 时，她才能出言不逊。珂愛想要知道，她至少需要操作多少次，才能让这个字符串的长度**大于等于** $L$。 如果你不告诉珂愛，珂愛会对你出言不逊。

第一行一个字符串 $S$。 第二行一个正整数 $L$。 意义见题目描述。

一行一个整数，表示最小操作次数。

nzhtl1477
15

2

### 样例解释 第一次操作，选择字符 `7`，字符串变为 `nzhtl147777`，长度为 $11$。 第二次操作，选择字符 `7`，字符串变为 `nzhtl1477777777`，长度为 $15$。 ### 限制与约定 对于 $100\%$ 的数据，$1\leq |S|\leq 10^6$，$1\leq L\lt 2^{64}$，$S$ 中只可能出现大、小写英文字母和数字，共 $62$ 种不同字符。 $|S|$ 表示字符串 $S$ 的长度。 本题共有 $4$ 个子任务，每个子任务的限制如下： 子任务 1（$15$ 分）：保证 $|S|=L-1$。 子任务 2（$20$ 分）：保证 $S$ 中只出现字符 `d`。 子任务 3（$30$ 分）：$L\leq 10^6$。 子任务 4（$35$ 分）：没有特殊限制。 ### 提示 **请注意 $L$ 的上限**。 **数据在 Windows 下生成，请注意每行的行末是 `\r\n` 而非 `\n`。**