无尽走廊

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

    2006年,我们可以称之为“帆“船年。一艘艘友谊的小船都在这一年翻掉了(当然也有升华为巨轮的)。然而这种事注定与小鱼无缘,就在不久前,小鱼与小驴刚吵了一架,在争吵的过程中,小鱼与小驴友谊的小木船失衡翻掉了。小鱼与小驴坠入大海,小鱼醒来后发现小驴不见了,慌张的小鱼四处寻找小驴,但小鱼发现小驴并不在小鱼身边。此时小鱼发现自己在一个大大的走廊尽头,走廊那边是无尽的黑暗,而小鱼身旁的一个告示牌上有如下内容:
    亲爱的人类啊~欢迎来到海洋之邸~想要找到你的朋友么~那就穿越这条无尽走廊吧~下面有一张魔法地图~可以带你通向海底堡~你的朋友就在那里等着你那~下面有一张魔法地图~可以带你离开这里~
    小鱼捡起地图,发现这条走廊是由好几条小走廊组成,地图上每条小走廊由一个大写英文字母表示。而小鱼现在在第一个字母处,出口在最后一个字母。
    地图上说,每个小走廊都有一扇时空之门,可以跳转到当前走廊往后第1~k个走廊处。而所需要的时间为两走廊字母编号的距离。譬如A走廊与B走廊间花费为1 Z与A花费为25 C与A花费为2。
    小鱼现在十分后悔跟小驴吵架。急切地想要找到小驴,你能帮小鱼算出一种方案,能够尽快找到小驴么?

Input

多组输入。
先输入一个整数T,表示组数。
之后每组先输入一个字符串(0 < 串长 <= 10^4),之后输入一个整数k(1 <= k <= 串长)表示每次最远移动距离。
每组输入占一行,以空格隔开。
 

Output

对于每组输入,输出一个正整数表示小鱼找到小驴的最短时间。每组输出占一行。

Sample Input

3
ACA 1
ACA 2
ABCA 2

Sample Output

4
0
2

Hint

对于第二组输入,在第一个走廊处往后移动两步,到达尽头。
对于第三组输入,在第一个走廊处先移动一步到达第二个走廊,再移动两步到达尽头,时间最短。
 

Source

“师创杯”山东理工大学第八届ACM程序设计竞赛 热身赛