#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

int main()

{

    int CA;

    cin>>CA;

    while(CA--){

        char str[],*start;

        int t,n,i,j,len,flag,h;

        start=&str[];

        scanf("%s %d",start,&n);

        len=strlen(start);

        for(i=;i<n;i++)

        {

            flag=-;

            for(j=len-;j>=;j--)

            {

                if((''<=start[j]&&start[j]<='')||('a'<=start[j]&&start[j]<'z')||('A'<=start[j]&&start[j]<'Z'))

                    {

                        start[j]++;flag=-;

                        break;

                    }

                else if(start[j]=='Z')     { start[j]='A';flag=j;}    /*最后一个底数在哪里*/

                else if(start[j]=='z')     {start[j]='a';    flag=j;}

                else if(start[j]=='')   {start[j]='';    flag=j;}

            }

            if(flag==-) start[len-]++;

            else if(flag>=)

            {

                start--;flag++;len++;

                for(j=;j<flag;j++)

                    start[j]=start[j+];

                if(start[flag]=='')

                start[flag-]='';

            }        

            for(j=;j<len;j++)

            printf("%c",start[j]);

            printf("\n");

        }

        printf("\n");

    }

    return ;

}

/*

4

***19 4

:-( 5

cirno=8 4

X 3

/**********/