String Shift Encoding

You are given a string \( s \) and an integer \( shift \). Your task is to encode the string by shifting each letter in \( s \) by \( shift \) positions in the English alphabet. The shifting is cyclic, meaning that after 'z' comes 'a' (and after 'Z' comes 'A'). Non-letter characters should remain unchanged.

Formally, for a letter \( c \) in the string:

• If \( c \) is a lowercase letter, it is replaced by \( \text{chr}(((\text{ord}(c)-\text{ord}('a')+shift) \mod 26)+\text{ord}('a')) \).
• If \( c \) is an uppercase letter, it is replaced by \( \text{chr}(((\text{ord}(c)-\text{ord}('A')+shift) \mod 26)+\text{ord}('A')) \).
• Otherwise, \( c \) is left unchanged.

Your solution must read from stdin and output the result to stdout.

inputFormat

The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a test case. A test case is provided as a single line which consists of a string \( s \) (which may contain spaces) followed by a space and an integer \( shift \).

Note: The integer is the last token in the line, and the rest of the line forms the string \( s \).

outputFormat

For each test case, output the encoded string on a new line.

## sample

4
hello 1
Zebra! 3
xyz 3
A 25

ifmmp
Cheud!
abc
Z

</p>