#include <fstream>

using namespace std;

ifstream fin ("a.in");
ofstream fout("a.out");

int n,x,b,i;

void f(int x,int b)
{
    if (x/b)
    {
        f(x/b,b);
        if (x%b>10)
        {
            fout << char(x%b-10+'A');
        }
        else fout << x%b;

    }
    else
    {
        fout << x%b;
    }
}


int main()
{
    fin >> n >> b;
    for (i=1;i<=n;i++)
    {
        fin >> x;
        f(x,b);
        fout<<'\n';
    }

    return 0;
}