题目描述

AZ国的科技十分发达，一直是各国觊觎的目标，XY国就是其中之一。经过XY国黑客夜以继日的奋斗，终于获得了AZ国World编码的转换方式，并且截获了n条原码。 BUT（总是有那么多但是~），XY国的黑客们呕心沥血研究World编码，都累得趴下了……所以，转换World编码的任务他们就无法完成。

XY国元首听说在遥远的东方国度，有一群才华横溢的少年——就是坐在电脑前的你们！元首希望你能够帮助XY国转换编码，重要的任务交给你们了！

World编码的转换规则如下： 对于每一条原码S，保证仅由26个大写字母组成。将每个字母后移R位，得到中转码S1（当S=‘XYZ’,R=2时，S1=‘ZAB’。即变成当前字母后R个字母，超过 ‘Z’则从‘A’开始）。接着，将中转码进行“符转数”操作，将S1每一位的ACS码（即ASCLL码）相乘，得到数串Q。转换后的编码即为Q。

元首为了检查你是不是偷懒，还要求你把中转码S1也输出。

输入格式

第1行，读入n，R。 第2~n+1行，每行一条编码S。

输出格式

共n*2行， 奇数行，每行一条中转码S1； 偶数行，每行一条转换后的编码Q。

样例数据

input

2 6
HELLOWORLD
LETUSGO

output

NKRRUCUXRJ
10167740864629920000
RKZAYMU
20957073637500

说明/提示

对于 30% 的数据，1≤n≤10,1≤R≤10；

对于 50% 的数据，1≤n≤500,1≤R≤10^3 ；

对于 100% 的数据，1≤n≤500,1≤R≤10^5 。

另外保证 原码长度小于600