#include <iostream>
#include <cmath>
 
using namespace std;
 
int power(int n){
int x;
const int max_x = 101010101;
if (n < 27) x = pow(2, n);
    else{
    x = pow(2, 27) - max_x;
        for (int i = 1; i <= n-27; i++){
            x *= 2;
                if (x > max_x)
                    x -= max_x;
        }
    }
return x;
}
 
int main(){
int t;
cin >> t;
    while(t--){
        int n, result;
        const int max_result = 101010101;
        cin >> n;
            if (n%2 == 0) result = 2*power(n/2);
            else result = power(n/2) + power((n+1)/2);
                    cout << result % max_result << '\n';
        }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IHBvd2VyKGludCBuKXsKaW50IHg7CmNvbnN0IGludCBtYXhfeCA9IDEwMTAxMDEwMTsKaWYgKG4gPCAyNykgeCA9IHBvdygyLCBuKTsKICAgIGVsc2V7CiAgICB4ID0gcG93KDIsIDI3KSAtIG1heF94OwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG4tMjc7IGkrKyl7CiAgICAgICAgICAgIHggKj0gMjsKICAgICAgICAgICAgICAgIGlmICh4ID4gbWF4X3gpCiAgICAgICAgICAgICAgICAgICAgeCAtPSBtYXhfeDsKICAgICAgICB9CiAgICB9CnJldHVybiB4Owp9CgppbnQgbWFpbigpewppbnQgdDsKY2luID4+IHQ7CiAgICB3aGlsZSh0LS0pewogICAgICAgIGludCBuLCByZXN1bHQ7CiAgICAgICAgY29uc3QgaW50IG1heF9yZXN1bHQgPSAxMDEwMTAxMDE7CiAgICAgICAgY2luID4+IG47CiAgICAgICAgICAgIGlmIChuJTIgPT0gMCkgcmVzdWx0ID0gMipwb3dlcihuLzIpOwogICAgICAgICAgICBlbHNlIHJlc3VsdCA9IHBvd2VyKG4vMikgKyBwb3dlcigobisxKS8yKTsKICAgICAgICAgICAgICAgICAgICBjb3V0IDw8IHJlc3VsdCAlIG1heF9yZXN1bHQgPDwgJ1xuJzsKICAgICAgICB9Cn0=

MgoyCjM=

2
2
3