Swagat has a string S consisting of lowercase English alphabets. He performs the following operation on his string S.

Choose an arbitrary alphabet from string and change it to the next corresponding alphabet.

Note: performing the operation on ‘z’ gives ‘a’.

e.g.- performing the operation on the 2^nd letter of ‘abf’ gives ‘acf’.

Help Swagat obtain the lexicographically smallest string after performing exactly K operations on the string S, and display the resultant string after K operations.

INPUT FORMAT:The first line contains a single integer 't' denoting the number of test cases.Each test case contains two lines,one containing the string s and the other containing the integer 'k'.

OUTPUT FORMAT:For each test case,print the lexicographically smallest string obtained after k operations.

Constraints:0<=t<=100,

0<=|s|<=1000,

0<=k<=10000