注：本题为C题“仓鼠很有精神”的升级版，请确保自己理解“音量值”机制再开此题。

现在，又有一排n名小仓鼠面对高年级大仓鼠，开始做自我介绍。每只鼠的自我介绍一开始都是固定的一个字符串。这次，为了让自己的自我介绍显得更有精神，仓鼠们可以对自己的自我介绍进行修改，具体方式是将其中任意一个字母改成自己想要的字母。但是每只仓鼠的口才不尽相同，所以能修改的字母数量也不尽相同。现在，大仓鼠希望你能告诉他，每只小仓鼠的自我介绍能达到的最大的音量值是多少。

第一行会给出一个整数n

接下来的n行，每行会有一个以小写字母组成的字符串s_i和一个整数k_i，分别表示这只仓鼠的自我介绍，以及这只仓鼠的口才能修改的字母总数。1≤s_i≤10⁶,0≤k_i≤s_i

我们保证所有小仓鼠的自我介绍的长度之和不超过5×10⁶，即∑s_i≤5×10⁶。

请注意，本题的背景与C题有关联，但数据范围与C题不同。

对于每一只仓鼠，你需要输出一行一个整数，表示答案。

k=1: henyoujingshen => henyouuingshen

k=3: henyoujingshen => heeeouuingshen