U461493 Strong Password 加强版

[原题链接](https://codeforces.com/contest/1997/problem/A)

Monocarp 在 Codeforces 上的当前密码是一个字符串 $s$，由小写拉丁字母组成。Monocarp 认为他当前的密码太弱了，所以他想在密码中插入 $k$ 个小写的拉丁字母以使其更强。Monocarp 可以选择任何字母并将其插入任何地方，甚至在第一个字符之前或最后一个字符之后。 Monocarp 认为密码的强度与他输入密码所花费的时间成正比。输入密码所需的时间按以下方式计算： 键入第一个字符的时间是 2 秒；对于除第一个字符以外的每个字符，如果它与前一个字符相同，键入它所需的时间为 1 秒，否则为 2 秒。 例如，键入密码 `abacaba` 所需的时间为 14 秒； 输入密码 `a` 所需的时间为 2 秒； 输入密码 `aaabacc` 所需的时间为 11 秒。 你必须帮助 Monocarp ——在他的密码中插入 $k$ 个小写的拉丁字母，这样生成的密码就会花费尽可能多的时间来输入。

第一行包含一个整数 $t$——数据的组数。 接下来一行一组数据，每组数据都由小写拉丁字母组成的字符串 $s$ 和一个整数 $k$ 组成。

对于每组数据，输出插入一个小写的拉丁字母的字符串具有的键入该字符串所需的最大可能时间。

$1\le t\le 1000$ $1\le k\le 1000$ $1\le |s|\le 1000$