2015年广东工业大学ACM校赛要来~\(≧▽≦)/~辣辣辣，作为校赛的出题人之一，GG想出了一道水题来考考大家。相信小伙伴们都学过字符串匹配，于是字符串匹配的水题就诞生辣！GG给出了一段长度为N的大写字母序列，现在他要你修改这一段字母序列，使得这段字母序列上最前面的K个字母组成的序列与最后面的K个字母组成的序列一一匹配。 
 
例如对于序列“ATUUUUAC”和K = 2，可以通过将第二个字母修改为“C”,使得最前面的两个字母与最后面的两个字母都为“AC”，当然 还存在其他的修改方法，现在GG要求你求出要使字符串匹配至少需要修改多少个字母。

有T组数据输入。（T <= 100） 
每组数据只有两行，第一行为一个字符串，第二行为一个正整数K，字符串的长度不会超过1000，且至少为1。（1 <= K <= N）。

对于每组数据输出至少需要修改的字母数量