SAMEBIT - 00 và 11

#include <iostream>
#include <algorithm>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <climits>
using namespace std;
const int mod = 123456789;
long long n, m;
long long power(long long a, long long b)
{
    if ( b == 0)
    {
        return 1;
    }
    long long t = power(a, b/2);
    if (b % 2 == 0)
    {
        return (t*t) % m;
    }
    else
    {
        return ((t*t)%m*a)%m;
    }
}
void read()
{
   cin >> n;
}
void solve()
{
   //n chẵn : (4^0 + 4^1 + .. 4^n/2)
   //n lẻ : 2 * (4^0 + 4^1 + .. + 4^(n/2) - 1)
   m = mod * 3;
   if (n % 2 == 0)
   {
       cout << (power(4, n/2) - 1)/3 << '\n';
   }
   else
   {
       cout << (2 * ((power(4, n/2) - 1)/3))%mod << '\n';
   }
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int t;
   cin >> t;
   while (t--)
   {
      read();
      solve();
   }
}