#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>#include <cassert>using namespace std;struct Str{char* str;int size;bool have;int sp;Str(char* s){str = s;size = strlen(str);reverse(str, str + size);have = checkHave();sp = 0;}bool checkHave(int i){if (str[i] <= '9' && str[i] >= '0') return 1;if (str[i] <= 'z' && str[i] >= 'a') return 1;if (str[i] <= 'Z' && str[i] >= 'A') return 1;return 0;}bool checkHave(){for (int i = 0; i < size; ++i){if (checkHave(i)) return 1;}return 0;}int next(){for (; sp < size; ++sp)if (checkHave(sp)) return sp++;return sp;}int increase(int k){bool carry = false;int ret;if (str[k] <= '9' && str[k] >= '0'){int tmp = (str[k] - '0' + 1); carry = (tmp == 10);str[k] = tmp % 10 + '0';ret = '1';}else if (str[k] <='z' && str[k] >='a'){int tmp = str[k] - 'a' + 1;carry = (tmp == 26);str[k] = tmp % 26 + 'a';ret = 'a';}else if(str[k] <= 'Z' && str[k] >= 'A'){int tmp = str[k] - 'A' + 1;carry = (tmp == 26);str[k] = tmp % 26 + 'A';ret = 'A';}else assert(0);return carry ? ret : 0;}void increase(){if (!have){str[0]++; have = checkHave(0);return ;}sp = 0;int last, now = next();int tmp;while (tmp = increase(now)){last = now;now = next();if (now == size){for (int i = size; i > last; --i)str[i + 1] = str[i];str[last + 1] = tmp;size++;break;}}}void out(){for (int i = size - 1; i >= 0; --i)printf("%c", str[i]);puts("");}};char str[200];int main(){int T;scanf("%d", &T);while (T--){scanf("%s", str);Str object = Str(str);int time;scanf("%d", &time);while(time--){object.increase();object.out();}puts("");}return 0;}
