#include <cstdio>

#define Mod 9999991

using namespace std;

long long Two[70];

void BuildTwo ()
{
    Two[0]=1;
    for (int i=1; i<64; ++i)
    {
        Two[i]=2*Two[i-1];
    }
}

int main()
{
    freopen ("ciuperci.in", "r", stdin);
    freopen ("ciuperci.out", "w", stdout);
    int T=0;
    scanf ("%d", &T);
    BuildTwo ();
    for (; T>0; --T)
    {
        long long N=0;
        scanf ("%lld", &N);
        for (int p=1; p<64; ++p)
        {
            if (Two[p]>N)
            {
                printf ("%lld\n", Two[p-1]%Mod);
                break;
            }
        }
    }
    return 0;
}