#include<bits/stdc++.h> using namespace std; const int MOD = 1000000000;

long long qpow(long long a, long long b) { long long res = 1; while(b > 0) { if(b % 2 == 1) { res = res * a % MOD; } a = a * a % MOD; b = b / 2; } return res; }

int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; if(n == 1) { cout << "1\n"; continue; } long long ans; int rem = n % 3; if(rem == 0) { ans = qpow(3, n / 3); } else if(rem == 1) { ans = qpow(3, n / 3 - 1) * 4 % MOD; } else { ans = qpow(3, n / 3) * 2 % MOD; } cout << ans << '\n'; } return 0; }