#include <stdio.h>
#define MAX_BITS 31
#define BIG 9901
int main(){
    int x[MAX_BITS][3][3] = {{{1,2,5},{1,0,0},{0,1,0}}};
    int w[3][3];
    int z[3];
    int test_count;
    int i, k, n;
    int row, col;
    int result;

    //Initialize...  Generate [power(2, i)] Matrix.
    for(i = 1 ; i < MAX_BITS ; ++i){
        for(row = 0 ; row < 3 ; ++row){
            for(col = 0 ; col < 3 ; ++col){
                //x[i][row][col] = 0;
                for(k = 0 ; k < 3 ; ++k){
                    x[i][row][col] += x[i-1][row][k] * x[i-1][k][col];
                    x[i][row][col] %= BIG;
                }
            }
        }
    }

    //Get TestCase Count
    scanf("%d", &test_count);
    while(test_count--){
        scanf("%d", &n);
        //Generate Identity Matrix
        for(row = 0 ; row < 3 ; ++row){
            for(col = 0 ; col < 3 ; ++col){
                if(row == col){
                    w[row][col] = 1;
                }
                else{
                    w[row][col] = 0;
                }
            }
        }
        //Generate Solution
        i = 0;
        while(n > 0 && i < MAX_BITS){
            if(n & 0x01){
                for(row = 0 ; row < 3 ; ++row){
                    for(col = 0 ; col < 3 ; ++col){
                        //Matrix Multiply
                        z[col] = 0;
                        for(k = 0 ; k < 3 ; ++k){
                            z[col] += w[row][k] * x[i][k][col];
                            z[col] %= BIG;
                        }
                    }
                    for(col = 0 ; col < 3 ; ++col){
                        w[row][col] = z[col];
                    }
                }
            }
            n >>= 1;
            ++i;
        }
        result = w[0][0];

        printf("%d\n", result);
    }
    return 0;
}