Well. Let's keep it simple. A  Caesar's cipher, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a right shift of 3, D would be replaced by G, E would become H, and so on. The method is named after Julius Caesar, who used it in his private correspondence.

Now little Aswin is enthralled on learning this new technique. He needs your help to create an application that performs this Caesar’s cipher.

Input

First line contains an integer T – the number of test cases.

Each test case consists of two lines. First line has the input text (length(input) <= 1000000) and the second has the number by which the text is to be shifted.

Output

The output text after the required operation is performed.

Examples

Input:
2
ABCDEFGHIJKLMNOPQRSTUVWXYZ
3
xyza
1

Output:
DEFGHIJKLMNOPQRSTUVWXYZABC
yzab