Sherlock Holmes and Dr Watson were on a mission to catch the world's greatest criminal mastermind i.e. Prof. Moriarty.

Dr Watson was successfully deceived at Reichenbach Falls and he left Holmes alone. When he returned back to the Falls he could find no one there but just a piece of paper.

On the paper Holmes had written 't' lines, each line consisted of a string 's' and an integer 'k'.

These strings were the name of the people involved in Moriarty's organization. Holmes knew that this paper could easily get into the hands of enemies so he encrypted the strings.

The integer 'k' is the key. The rule of the encryption is that each alphabet is cyclically rotated for 'k' times i.e. if k=14 then 'a' becomes 'o' and 'n'='b' (think carefully).

Dr Watson is already in a shock of losing Holmes so please help him out by decrypting the string and help police to put those criminals behind the bars.

Note: The String 's' consists of just lower-case letters and upper-case letters.

Input

Input consists of 't' test cases. Each test case consists a string 's' and an integer 'k'.

Output

On a new line output the decrypted string .

Constraint

1 <= t <= 10
1 <= length of string <= 100
1 <= k < 100

Example

Input:
3
an 14
abc 5 
DfIzrikp 9

Output:
ob
fgh
MoRiarty