A7504 | $午枫的密码本$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

午枫在宝箱中除了金币和罗盘，还找到了一本古老的密码本。密码本上有一个由小写字母构成的字符串 $S$。 经过研究，他发现真正的密码并不是 $S$ 本身，而是将 $S$ 重复拼接 $k$ 次后得到的新字符串 $S'$ 中 严格递增子序列 的长度。 这里 子序列 指的是删除若干个字符（可以是 $0$ 个或全部删除）后，保持其他字符的原有顺序得到的新字符串。 所谓 严格递增子序列 ，是指子序列中每个字符的 ASCII 码严格大于前一个字符。 午枫需要计算出 $S'$ 的最长严格递增子序列的长度，才能继续解读下一道密文。

本题包含多组测试数据。 第一行一个正整数 $T$（$1 \le T \le 20$），表示数据组数。 接下来 $T$ 行，每行一个字符串 $S$ 和一个正整数 $k$，中间用空格隔开。 其中： - $1 \le |S| \le 100$ - $1 \le k \le 10^{100}$ $k$ 可能非常大，需要使用高精度或字符串读入。

对于每组数据，输出一行一个正整数，表示 $S'$ 的最长严格递增子序列的长度。

输入 #1

1
yummy 2

输出 #1

C++ 编辑器

输入

输出