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

int main() {
    
    int max = 1000005;
    int mod = 9973;
    int ok;
    
    FILE *f = fopen("ssnd.in","rt"), *g = fopen("ssnd.out","wt");
    int j,i,t,n,k = 0;
    
    int p[1000005];
    int viz[1000005] = {0} ;
    for (i = 2; i <= max; i++){
        if (viz[i] == 0)
         {
                   viz[i] = 1; 
                   p[k] = i; k++;
                   for (j = i+i; j <= max; j+= i){
                       viz[j] = 1;
                   }
         }
    }
    
    fscanf(f,"%i",&t);
    int sum = 1,put;
    k = 0;
    for (i = 1; i <= t; i++){
        fscanf(f,"%i",&n);
        sum = (1+n) % mod;
        while (n != 1 && k <=max) {
              if (n % p[k] == 0){
                 sum = (sum + p[k]) % mod;
                   ok = 1;
                   put = p[k];
                   n = n / p[k];
                   while (ok)
                   {
                         if (n % p[k] == 0)
                         {n = n  / p[k];
                         put = put * p[k];
                         sum = (sum + put) % mod;
                               }
                         else ok =0;
                         }     
                         k++;
              }
              else k++; 
        }
        sum = (sum + n) % mod;
        fprintf(g,"%i\n",sum);
    }
    
     
    fclose(f);
    fclose(g);
    
    
    
    
    
    
    return 0;
}