Description

珂愛想出公开赛，但每次都被拒绝。

珂愛很生气，于是学会了出言不逊。

珂愛用一个字符串 $S$ 存储了她想说的话，但这句话太逊了。为了出言不逊，珂愛要对字符串进行操作。每次操作，珂愛可以选择一个字符 $c$，若 $c$ 在字符串 $S$ 中出现了 $x$ 次，则珂愛会将 $x$ 个字符 $c$ 补到 $S$ 的尾部。

珂愛认为，这个字符串长度至少为 $L$ 时，她才能出言不逊。珂愛想要知道，她至少需要操作多少次，才能让这个字符串的长度大于等于 $L$。

如果你不告诉珂愛，珂愛会对你出言不逊。

Input Format

第一行一个字符串 $S$。

第二行一个正整数 $L$。

意义见题目描述。

Output Format

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

nzhtl1477
15

2

Hint

样例解释

第一次操作，选择字符 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。