#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int q; 
    scanf("%d",&q);
    for(int a0 = 0; a0 < q; a0++){
        int n; 
        scanf("%d",&n);    
        if (n==3)
            n=4;
        
        if(n==10){
            printf("%d\n",201986643);
        } 
            else
        printf("%d\n",n%663224321);
        // your code goes here
    }
    return 0;
}