#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char s1[16]="0123456789ABCDEF";//auxiliar strings
char s2[16]="0123456789abcdef";

int num(char c,int p)//return the value of the digit
{
    int i=0;
    while (i<p)
    {
        if ((s1[i]==c) || (s2[i]==c))
        {
            return i;
        }
        i++;
    }
    return -1;
}

void insert(char c,char* s,int k)
{
    int i;
    for (i=strlen(s)+1;i>=k+1;i--)
    {
        s[i]=s[i-1];
    }
    s[i]=c;
}

void cut_0(char *s)//cuts the zeroes from the left side
{
    while ((s[0]=='0') && (strlen(s)!=1))
    {
        int j;
        for (j=0;j<=strlen(s)-1;j++)
        {
            s[j]=s[j+1];
        }
    }
}

void addition(char* a,char* b,char* c,int p)
{
    int carry=0;
    int k=strlen(a)-1,l=strlen(b)-1;
    while ((k>=0) && (l>=0))//while both number are digit on the current poisition
    {
        insert(s1[(num(a[k],p)+num(b[l],p)+carry)%p],c,0);//insert on the first position the suitable digit
        carry=(num(a[k],p)+num(b[l],p)+carry)/p;
        k--;
        l--;
    }
    if ((k<0) && (l>=0))//if the second number has more digits than the first one
    {
        while (l>=0)
        {
            insert(s1[(num(b[l],p)+carry)%p],c,0);
            carry=(num(b[l],p)+carry)/p;
            l--;
        }
    }
    else if ((k>=0) && (l<0))//if the first number has more digits than the firt one
    {
        while (k>=0)
        {
            insert(s1[(num(a[k],p)+carry)%p],c,0);
            carry=(num(a[k],p)+carry)/p;
            k--;
        }
    }
    if (carry==1)//if exists carry then inserts it
    {
        insert('1',c,0);
    }
}

void subtraction(char* a,char* b,char* c,int p,int *neg)
{
    if ((strlen(a)<strlen(b)) || (strlen(a)==strlen(b)))//if the minuend is less than the subtrahend the reverse the numbers and the result will be negative
    {
        int q=1;
        if (strlen(a)==strlen(b))
        {
            int i=0;
            while ((a[i]==b[i]) && (i+1!=strlen(a)))
            {
                i++;
            }
            if ((i!=strlen(a)) && (a[i]<b[i]))
            {
                q=1;
            }
            else
            {
                q=0;
            }
        }
        if (q==1)
        {
            char temp[100];
            int i;
            for (i=0;i<=strlen(a);i++)
            {
                temp[i]=a[i];
            }
            for (i=0;i<=strlen(b);i++)
            {
                a[i]=b[i];
            }
            for (i=0;i<=strlen(temp);i++)
            {
                b[i]=temp[i];
            }
            *neg=1;
        }
    }
    int carry=0;
    int k=strlen(a)-1,l=strlen(b)-1;
    while ((k>=0) && (l>=0))//while both number has digit in the current position
    {
        if (num(a[k],p)-num(b[l],p)+carry>=0)
        {
            insert(s1[num(a[k],p)-num(b[l],p)+carry],c,0);
            carry=0;
        }
        else
        {
            insert(s1[num(a[k],p)-num(b[l],p)+carry+p],c,0);
            carry=-1;
        }
        k--;
        l--;
    }
    if ((k>=0) && (l<0))//if the minuend has more digits
    {
        while (k>=0)
        {
            if (num(a[k],p)+carry>=0)
            {
                insert(s1[num(a[k],p)+carry],c,0);
                carry=0;
            }
            else
            {
                insert(s1[num(a[k],p)+carry+p],c,0);
                carry=-1;
            }
            k--;
        }
    }
    cut_0(c);
}

void multiplication(char *a,char* b,char *c,int p)
{
    int i;
    for (i=strlen(b)-1;i>=0;i--)//for every digits from the second number will be executed the multiplication
    {
        char temp[strlen(a)+strlen(b)];
        temp[0]='\0';
        int carry=0,j;
        for (j=0;j<strlen(b)-1-i;j++)//more and more zeroes have to wil be on the right side of the subresults of multiplication
        {
            insert('0',temp,0);
        }
        for (j=strlen(a)-1;j>=0;j--)
        {
            insert(s1[(num(b[i],p)*num(a[j],p)+carry)%p],temp,0);
            carry=(num(b[i],p)*num(a[j],p)+carry)/p;
        }
        char d[200];
        d[0]='\0';
        insert((char)carry+'0',temp,0);
        addition(temp,c,d,p);//addition of the subresult
        for (j=0;j<=strlen(d);j++)
        {
            c[j]=d[j];
        }
    }
    cut_0(c);
}

void division(char* a,char* b,char* q,char *r,int p)
{
    int i,carry=0;
    for (i=0;i<strlen(a);i++)//for every digit of the dividend
    {
        insert(s1[(carry*p+num(a[i],p))/num(b[0],p)],q,strlen(q));
        carry=(carry*p+num(a[i],p))%num(b[0],p);
    }
    *r=s1[carry];
    cut_0(q);
}

void conversion(char* a,int p,int q)
{
    if (p>q)//if p>q then the used algorithm is the successive division by the destination base
    {
        char b[100];
        b[0]='\0';
        if ((a[0]=='0') && (a[1]=='\0'))
        {
            b[0]='0';
            b[1]='\0';
        }
        while ((a[0]!='0') || (a[1]!='\0'))//while the dividend is not zero
        {
            char quo[100],rem;
            quo[0]='\0';
            division(a,&s1[q],quo,&rem,p);
            insert(rem,b,0);
            int i;
            for (i=0;i<=strlen(quo);i++)
            {
                a[i]=quo[i];
            }
        }
        int i;
        for (i=0;i<=strlen(b);i++)
        {
            a[i]=b[i];
        }
    }
    else if (p<q)//if p<q then the used algorithm is the substitution method
    {
        char b[100];
        b[0]='0';
        b[1]='\0';
        int i=0;
        while (i<strlen(a))//the algorithm is used for every digit from the number
        {
            char res[100];
            res[0]=a[i];
            res[1]='\0';
            int j;
            for (j=1;j<=strlen(a)-i-1;j++)//multiplication of current digit with the suitable power of the base p
            {
                char temp[100];
                temp[0]='\0';
                char c[2];
                c[0]=s1[p];
                c[1]='\0';
                multiplication(res,&c,temp,q);
                int k;
                for (k=0;k<=strlen(temp);k++)
                {
                    res[k]=temp[k];
                }
            }
            char temp[100];
            temp[0]='\0';
            addition(b,res,temp,q);
            for (j=0;j<=strlen(temp);j++)
            {
                b[j]=temp[j];
            }
            i++;
        }
        for (i=0;i<=strlen(b);i++)
        {
            a[i]=b[i];
        }
    }
    cut_0(a);
}

void rap_conv(char* a,int p,int q)
{
    if (p!=2)//if the source base is not 2 then it will be converted in base 2
    {
        char b[100];
        b[0]='\0';
        int gr;
        switch (p)
        {
            case 4: gr=2; break;
            case 8: gr=3; break;
            case 16: gr=4; break;
        }
        int i;
        for (i=strlen(a)-1;i>=0;i--)//convert digit by digit to base 2
        {
            char temp[5];
            temp[0]=a[i];
            temp[1]='\0';
            conversion(temp,p,2);
            int j;
            int k=strlen(temp);
            for (j=1;j<=gr-k;j++)
            {
                insert('0',temp,0);
            }
            for (j=gr-1;j>=0;j--)
            {
                insert(temp[j],b,0);
            }
        }
        for (i=0;i<=strlen(b);i++)
        {
            a[i]=b[i];
        }
    }
    cut_0(a);
    if (q!=2)
    {
        char b[100];
        b[0]='\0';
        int gr;
        switch (q)
        {
            case 4: gr=2; break;
            case 8: gr=3; break;
            case 16: gr=4; break;
        }
        int i;
        for (i=1;i<=strlen(a)%gr;i++)//if there does not exist enough number of digits then it is completed by zeroes
        {
            insert('0',a,0);
        }
        for (i=strlen(a)/gr-1;i>=0;i--)//every groups of number containing gr number of digits is converted to the base q
        {
            char temp[5];
            int j;
            for (j=i*gr;j<=(i+1)*gr-1;j++)
            {
                temp[j-i*gr]=a[j];
            }
            temp[gr]='\0';
            conversion(temp,2,q);
            insert(temp[0],b,0);
        }
        for (i=0;i<=strlen(b);i++)
        {
            a[i]=b[i];
        }
    }
    cut_0(a);
}

int main()
{
    long int t,k,i;
    scanf("%d %d",&t,&k);
    long int a[100000];
    for (i=0;i<t;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<t;i++)
    {
        char s[1000000];
        s[0]='\0';
        long int j;
        for (j=0;i<a[i];j++)
        {
            long int c;
            for (c=0;c<k;c++)
            {
                insert('0',s,0);
            }
            insert('1',s,0);
        }
        conversion(s,2,10);
        char b[7]="666013\0";
        char q[100000],r[1000000];
        q[0]='\0';
        r[0]='\0';
        division(s,b,q,r,10);
        printf("%s\n",r);
    }
    return 0;
}