#include <fstream>
#include <cmath>
#include <bitset>
#define P 9973

using namespace std;
ifstream fi ("ssnd.in");
ofstream fo ("ssnd.out");

struct structura{long long el,nr;} divizor[300006];
bitset <1000006> fr;
long long T,numar,i,j,nrprime,nrdiv;
long long prim[300006];

void precalculare()
{
  for (i=2;i<=1000000;i++)
    if (!fr[i])
    {
      for (j=i+i;j<=1000000;j=j+i) fr[j]=1;
      nrprime++;
      prim[nrprime]=i;
    }
}

long long putere(long long baza,long long exponent)
{
  baza=baza%P;
  if (exponent==1) return baza%P;
  if (exponent%2==0) return putere(baza*baza,exponent/2)%P;
  if (exponent%2==1) return baza*putere(baza,exponent-1)%P;
}

void aflare_nrdiv(long long x)
{
  long long iprim;
  long long sol=1;
  nrdiv=0;
  for (iprim=1;prim[iprim]<=sqrt(x+.01) and iprim<=nrprime;iprim++)
  if (x%prim[iprim]==0)
  {
    nrdiv++;
    divizor[nrdiv].el=prim[iprim];
    long long cnt=0;
    while (x%prim[iprim]==0)
    {
      x=x/prim[iprim];
      cnt++;
    }
    divizor[nrdiv].nr=cnt;
    sol=sol*(cnt+1);
  }
  if (x>1)
  {
    nrdiv++;
    divizor[nrdiv].el=x;
    divizor[nrdiv].nr=1;
    sol=sol*2;
  }
  fo<<sol<<' ';
}

void aflare_sumdiv()
{
  long long sol=1;
  for (i=1;i<=nrdiv;i++)
  {
    long long numarator=putere(divizor[i].el,divizor[i].nr+1)-1;
    long long invmod=putere(divizor[i].el-1,P-2);
    sol=sol*numarator;
    sol=sol%P;
    sol=sol*invmod;
    sol=sol%P;
  }
  fo<<sol<<'\n';
}
int main()
{
    precalculare();
    fi>>T;
    while (T)
    {
      T--;
      fi>>numar;
//      aflare_nrdiv(numar);
//      aflare_sumdiv();
    }
    return 0;
}