#include<iostream>
#include<vector>
#include<algorithm>
#include <bits/stdc++.h>
using namespace std;

//投机取巧，找规律，数量大于62500时，每62500个数作为一个循环，保留的六位数为109376
int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        int sum=1;
        if(x<62500) {
            while (x--) {
                sum *= 2;
                if (sum > 999999)
                    sum %= 1000000;
            }
            cout << sum - 1 << endl;
        }
        else
        {
            x%=62500;
            sum=109376;
            while (x--) {
                sum *= 2;
                if (sum > 999999)
                    sum %= 1000000;
            }
            cout << sum - 1 << endl;
        }
    }
    return 0;
}