#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <numeric>
#include <cassert>
#include <cmath>
#include <string>
#include <sstream>

using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)

int N,T;

struct NSTATE
{
	int score;//the score of the current state
	int sumc;//auxiliary variable help the calculation for the next state
	int usedPosMask;//which position are used (if we sort the letters)
	int usedLetterMask;//which letters already used
	int parent;//auxiliary variable for calculate the answer after find an answer

	bool operator<(const NSTATE& other) const
	{
		return score > other.score;
	}
	bool operator==(const NSTATE& other) const
	{
		return score == other.score && usedPosMask == other.usedPosMask && usedLetterMask == other.usedLetterMask;
	}
	int calculateScore()
	{//heuristic score of the current state
		score = 10000000;
		int pos = 0, letter = 0, last_used_pos = 0, last_used_letter = 0;
		while (pos <= N && letter <= 26)
		{
			if (!(usedPosMask & (1 << pos)) && pos < N)
				++pos;
			if (!(usedLetterMask & (1 << letter)) && letter < 26)
				++letter;
			if (((usedPosMask & (1 << pos)) && letter == 26) || (pos == N && (usedLetterMask & (1 << letter))))
			{
				score = 0;
				break;
			}
			if (((usedPosMask & (1 << pos)) && (usedLetterMask & (1 << letter))) || (pos == N && letter == 26))
			{
				int pos_gap = pos - last_used_pos + 1;
				int letter_gap = letter - last_used_letter + 1;
				if (pos_gap > letter_gap)
				{
					score = 0;
					break;
				}
				if(pos_gap>1)
					score = min(score, letter_gap*10000 / (pos_gap + 1));
				last_used_pos = ++pos;
				last_used_letter = ++letter;
			}
		}
		return score ;
	}
	
	void calculateChildren(vector<NSTATE>& outres, int parent_index, int targ) const
	{//calculate how we can go further from the current state
		int pos = 0, letter = 0, last_used_pos = 0, last_used_letter = 0;
		while (pos <= N && letter <= 26)
		{
			if (!(usedPosMask & (1 << pos)) && pos < N)
				++pos;
			if (!(usedLetterMask & (1 << letter)) && letter < 26)
				++letter;
			if (((usedPosMask & (1 << pos)) && letter == 26) || (pos == N && (usedLetterMask & (1 << letter))))
			{
				break;
			}
			if (((usedPosMask & (1 << pos)) && (usedLetterMask & (1 << letter))) || (pos == N && letter == 26))
			{
				NSTATE newCandidate;
				newCandidate.parent = parent_index;
				FOR(new_letter, last_used_letter, letter)//run all of the possible characters
				{
					int z = (targ + 10 - sumc + 10 - new_letter)%10;
					newCandidate.sumc = (sumc + new_letter) % 10;
					newCandidate.usedLetterMask = usedLetterMask | (1 << new_letter);
					while(z<pos)
					{
						if(z >= last_used_pos)
						{
							newCandidate.usedPosMask = usedPosMask | (1 << z);
							newCandidate.calculateScore();
							if (newCandidate.score)
								outres.push_back(newCandidate);
						}
						z +=10;
					}
				}
				last_used_pos = ++pos;
				last_used_letter = ++letter;
			}
		}
	}
};

string solver(LL query)
{
	vector<vector<NSTATE> > w(N + 1);
	NSTATE start;
	start.sumc = start.usedLetterMask = start.usedPosMask = 0;
	int BEAM_WIDTH = 4;
	while(w[N].empty() || w[N][0].score == 0)
	{
		REP(i,N)
			w[i].clear();
		w[0].push_back(start);
		LL qr = query;
		REP(i, N)
		{
			int digit =  qr % 10;
			qr /= 10;
			vector<NSTATE>& act = w[i];
			REP(j, min<int>(act.size(), BEAM_WIDTH))
			{
				act[j].calculateChildren(w[i + 1], j, digit);
			}
			sort(w[i + 1].begin(), w[i + 1].end());
		}
		BEAM_WIDTH *= 2;//if we don't find an anser make the next beam search wider
	}
	
	//calculate the answer
	string answer(N, 'a');
	int i = N, j = 0;
	while (i)
	{
		int mask = w[i][j].usedLetterMask ^ w[i - 1][w[i][j].parent].usedLetterMask;
		REP(k, 26) if ((1 << k)&mask)
		{
			answer[N - i] += k;
			break;
		}
		j = w[i][j].parent;
		--i;
	}
	return answer;
}

int main(int argc, char** argv) {
#ifdef HOME
	freopen("in.txt", "rb", stdin);
	freopen("out.txt", "wb", stdout);
#endif
	scanf("%d %d", &T, &N);
	while (T--)
	{
		LL query;
		scanf("%lld", &query);
		string z = solver(query);
		printf("%s\n", z.c_str());
	}
	return 0;
}