#include <stdio.h>
#include <ctype.h>

const long long MOD = 666013;

const int precomp_pow2_mod[]=
    {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,
     262144,524288,382563,99113,198226,396452,126891,253782,507564,349115,32217,
     64434,128868,257736,515472,364931,63849,127698,255396,510792,355571,45129,
     90258,180516,361032,56051,112102,224204,448408,230803,461606,257199,514398,
     362783,59553,119106,238212,476424,286835,573670,481327,296641,593282,520551,
     375089,84165,168330,336660,7307,14614,29228,58456,116912,233824,467648,269283,
     538566,411119,156225,312450,624900,583787,501561,337109,8205,16410,32820,
     65640,131280,262560,525120,384227,102441,204882,409764,153515,307030,614060,
     562107,458201,250389,500778,335543};


int main()
{
    int t,k; scanf("%d %d",&t,&k);
    
    long long k_pow=precomp_pow2_mod[k];
    long long k1_pow=precomp_pow2_mod[k+1];

    int nr_cic=1;
    int rest[MOD];
    rest[0]=0;

    long long nr=k_pow;
    while(nr!=0){
        rest[nr_cic++]=nr;
        nr= (nr*k1_pow + k_pow)%MOD;
    }

    char buff[1000005];
    fgets(buff, 1000005, stdin); 

    for(int i=0;i<t;++i){
        int r=0;
        fgets(buff,1000005,stdin); 
               

        for(unsigned j=0;isdigit(buff[j]);++j) 
            r=(r*10+buff[j]-'0')%nr_cic;

        printf("%d\n",rest[r]);
    }
}