文件目录

#include <bits/stdc++.h>
using namespace std;
int a[10005] = {};
long long ksm(long long b, long long p, long long k)
{
    long long ans = 1;
    while (p)
    {
        if (p % 2)
        {
            ans *= b;
            ans %= k;
        }
        p /= 2;
        b = b * b;
        b %= k;
    }
    return ans;
}
void init()
{
    for (int i = 0; i < 10005; i++)
        a[i] = ksm(2011, i, 10000);
}
int main()
{
    init();
    int k;
    cin >> k;
    string n;
    while (k--)
    {
        cin >> n;
        if (n.size() > 5)
            n = n.substr(n.size() - 5);
        cout << a[stoi(n) % 10000] << endl;
    }
    return 0;
}