//
//  Cifra.cpp
//  
//
//  Created by Raoul Bocancea on 20/11/2018.
//

#include <fstream>

const std :: string programName = "cifra";
std :: ifstream f(programName + ".in");
std :: ofstream g(programName + ".out");

const int MOD = 1999999973;

inline int ult(int x) { return x % 10; }

int pow(int, int);

int main(void) {
    int T;
    f >> T;
    while (T--) {
        int s = 0, N;
        f >> N;
        for (int i = 1; i <= N; ++i) {
            int temp = pow(i, i);
            s += temp;
        }
        g << ult(s) << '\n';
    }
    return 0x0;
}

int pow(int N, int P) {
    int64_t sol = 1, Xcopy = N;
    for (int i = 0; (1 << i) <= P; ++i) {
        if ((1 << i) & P)
            sol = (sol * Xcopy) % MOD;
        Xcopy = (Xcopy * Xcopy) % MOD;
    }
    return sol;
}