凯撒密码（英语：Caesar cipher），是一种最简单且最广为人知的加密技术。凯撒密码是一种替换加密技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例如，当偏移量是 3 的时候，所有的字母 "A" 将被替换成 "D"，"B" 变成 "E"，以此类推。这个加密方法是以罗马共和时期凯撒的名字命名的，据称当年凯撒曾用此方法与其将军们进行联系。

凯撒密码的替换方法是通过排列明文和密文字母表，密文字母表示通过将明文字母表向左或向右移动一个固定数目的位置。例如，当偏移量是左移 3 的时候（解密时的密钥就是 3）：

明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

使用时，加密者查找明文字母表中需要加密的消息中的每一个字母所在位置，并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作，得到原来的明文。例如：

明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ

简单来说，当偏移量为 k 时，则将原文中的每一个字母用其后的第 k 个字母来替代，字母 "Z" 后面的字母为 "A"，以此循环。 如果明文内包含空格，则暗文相应位置也为空格，不做改动。

本题为多实例，先输入一行一个正整数 T (1 ≤ T ≤ 100)，表示查询的个数。

对于每次查询，先输入一行两个整数 n, k (1 ≤ n ≤ 10⁵, -1000 ≤ k ≤ 1000)，分别表示字符串的长度和凯撒密码的偏移量。

然后输入一个长度为 n 的字符串 s，表示需要加密的明文，明文中只包含大写字母及空格，且行首行末不包含空格。

保证所有样例中 n 的和不超过 10⁵。