Dada una cadena S de longitud n, para obtener una subcadena de S, podemos agarrar dos indices i, j tal que 1 <= i <= j <= n, y formar una nueva cadena con todos los caracteres de S en el rango [i, j], en el mismo orden que aparecen en S.

Asignemos a cada caracter su valor distancia con la 'a', por ejemplo:

'a' = 0

'b' = 1

'c' = 2

Sea S es una cadena de longitud n, y S[i] es el caracter i-esimo de S, definamos las funciones:

f(S) = S[1] + S[2] + .. + S[n]

R(S) =   { si S[i] es 'z' entonces S[i] = 'a'

             { sino S[i] toma el siguiente caracter en el alfabeto

Jose esta jugando con una cadena S de longitud n.

Jose guarda todas las subcadenas de S en una bolsa.

En cada turno Jose escoge usar una subcadena T de la bolsa y sumar el valor de f(T) a su puntaje.

Despues de usar una subcadena T Jose desecha esa subcadena, pero puede insertar R(T) a la bolsa.

La entrada comienza con el numero de casos a considerar t.

Las siguientes t lineas, contienen una cadena S de longitud n y un entero k que representa la cantidad de turnos de Jose.

S solo contiene letras de la 'a' a la 'z'

1 <= n <= 1000

1 <= k <= 1000