include <bits/stdc++.h>

using namespace std;

long long MOD (1e9+7); long long binary_expo(long long a, long long b){ if(b < 0) return 1; long long product = 1; while(b){ if(b & 1) product = (product * a) % MOD; a = (a * a) % MOD; b >>= 1; } return product; }

int locker(int n){ long long answer = 1; if(n == 1) return answer; if(n < 3) return n; if(n % 3 == 0) { return (binary_expo(3, n / 3) % MOD); } if(n % 3 == 1){ n -= 4; return (4 * binary_expo(3,n / 3) % MOD); } else { n -= 2; return (2 * binary_expo(3, n / 3) % MOD); } }

int main() { int t; cin>>t; while(t--){ int n; cin>>n; cout<<locker(n)<<endl; } return 0; }