#include<bits/stdc++.h>
using namespace std;
long long n,r,x;
string a;
long long l,ans[30000];
int main(){
	cin >> n >> r;
	r%=26;
	while(n--){
		fill(ans,ans+l,0);
		ans[1]=1;
		l=1;
		cin >> a;
		for(int i=0;i<a.size();i++){
			x=(a[i]-'A'+r)%26+'A';
			a[i]=x;
			int jw=0;
			for(int j=1;j<=l;j++){
				ans[j]=ans[j]*x+jw;
				jw=ans[j]/10;
				ans[j]%=10;
				if(jw!=0&&j==l){
					l++;
				}
			}
		}
		cout << a << endl;
		for(int i=l;i>0;i--)cout << ans[i] ;
		cout << endl;
	}
	return 0;
}