A141177.午枫的密码本

午枫在宝箱中除了金币和罗盘，还找到了一本古老的密码本。密码本上有一个由小写字母构成的字符串 $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 \le T \le 20$
• $1 \le |S| \le 100$
• $1 \le k \le 10^{100}$