问题 D: 学 DP 导致的

DP 的一个经典应用便是求最长上升子序列。本题中，子序列指的是删除若干个字符（可以是 $0$ 个或全部删除）后，保持其他字符的原有顺序得到的新字符串。

给出一个小写字母构成的字符串 S，将 S 拼接 k 次后会得到一个新字符串 S′。

求 S′ 最长的子序列长度，使得子序列中字符的 ASCII 码严格递增。

本题有多组数据。 输入的第一行有一个正整数 $T$（1≤T≤20），表示数据组数。

对于每组数据，输入一行，包括一个字符串 S(1≤∣S∣≤100)和一个正整数 k(1≤k≤10100)，含义同题目描述。

【样例解释】

S′S′ 为 yummyyummy，最长的符合题意的子序列为 muy。