#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 666013;


int main()
{
    int t,k; cin>>t>>k;

    long long k_pow=1;
    for(int i=0;i<k;++i) k_pow=(k_pow)*2%MOD;
    long long k1_pow=k_pow*2%MOD;

    int nr_cic=1;
    vector<long long> rest(MOD);
    rest[0]=0;

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

    cin.ignore(100,'\n'); // '\n' on the first line

    char buff[1000005];

    for(int i=0;i<t;++i){
        // calculate (huge_nr) modulo (nr_cic)
        int r=0;
        cin.get(buff,1000004);        

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

        cout<<rest[r]<<'\n';
    }

}