t = int(input())
for i in range(t):
    n = int(input())
    ans = 1
    while n > 3:
        n //= 4
        ans *= 2
    print(ans)

import sys
 
sys.set_int_max_str_digits(6000)
 
def fact(x):
    if x == 0:
        return 1
    return x * fact(x - 1)
 
t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    n = min(n, 7)
    s = int(str(k) * fact(n))
    for i in range(1, 10, 2):
        if s % i == 0:
            print(i, end = ' ')
    print()

for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l1, r1 = 0, 0
	l2, r2 = 2*10**9, -2*10**9
	
	pr = 0
	mnl, mxl = 0, 0
	mnr, mxr = 2*10**9, -2*10**9
	for i in range(n):
		pr += a[i]
		if a[i] != -1 and a[i] != 1:
			mnr, mxr = mnl, mxl
			mnl, mxl = pr, pr
		l1 = min(l1, pr - mxl)
		r1 = max(r1, pr - mnl)
		l2 = min(l2, pr - mxr)
		r2 = max(r2, pr - mnr)
		mnl = min(mnl, pr)
		mxl = max(mxl, pr)
	res = []
	if l2 > r1:
		res = list(range(l1, r1 + 1)) + list(range(l2, r2 + 1))
	elif r2 < l1:
	    res = list(range(l2, r2 + 1)) + list(range(l1, r1 + 1))
	else:
		res = list(range(min(l1, l2), max(r1, r2) + 1))
	print(len(res))
	print(*res)

#include<bits/stdc++.h>
 
using namespace std;
 
long long gcd(long long x, long long y)
{
    if(x == 0) return y;
    else return gcd(y % x, x);
}
 
void solve()
{
    long long l, r, g;
    scanf("%lld %lld %lld", &l, &r, &g);
    long long L = l + (l % g == 0 ? 0 : g - (l % g));
    long long R = r - r % g;
    for(int i = 0; i <= (R - L) / g; i++)
        for(int j = 0; j <= i; j++)
            if(gcd(L + j * g, R - (i - j) * g) == g)
            {
                printf("%lld %lld\n", L + j * g, R - (i - j) * g);
                return;
            }   
    puts("-1 -1");
}
 
int main()
{                             
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) solve();
}

#include<bits/stdc++.h>
 
using namespace std;
 
struct graph
{
    int V;
    vector<vector<int>> g;
    vector<int> color;
 
    bool dfs(int v)
    {
        if(color[v] != 0) return false;
        color[v] = 1;
        bool res = false;
        for(auto y : g[v])
        {
            if(color[y] == 2) continue;
            else if(color[y] == 0)
                res |= dfs(y);
            else res = true;
        }
        color[v] = 2;
        return res;
    }
 
    void add_edge(int x, int y)
    {
        g[x].push_back(y);
    }
 
    graph(int V)
    {
        this->V = V;
        this->g.resize(V);
        this->color.resize(V);
    };
};
 
int get_bit(int x, int y)
{
    return (x >> y) & 1;
}
 
bool check(const vector<vector<int>>& a, const vector<vector<int>>& b, int k)
{
    int n = a.size();
    int m = a[0].size();
    vector<bool> must_row(n);
    vector<bool> must_col(m);
    auto G = graph(n + m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(get_bit(a[i][j], k) != get_bit(b[i][j], k))
            {
                if(get_bit(b[i][j], k) == 0) must_row[i] = true;
                else must_col[j] = true;
            }
            if(get_bit(b[i][j], k) == 0) G.add_edge(j + n, i);
            else G.add_edge(i, j + n);
        }                 
    for(int i = 0; i < n; i++)
        if(must_row[i] && G.dfs(i))
            return false;
    for(int j = 0; j < m; j++)
        if(must_col[j] && G.dfs(j + n))
            return false;
    return true;
}
 
void solve()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    auto b = a;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &b[i][j]);
    for(int i = 0; i < 30; i++)
    {
        if(!check(a, b, i))
        {
            puts("No");
            return;
        }
    }
    puts("Yes");
}
 
int main()
{                             
    int t;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++) 
 
const int MOD = 998244353;
 
int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	return a;
}
 
int mul(int a, int b){
	return a * 1ll * b % MOD;
}
 
struct state{
	int mx, cnt;
};
 
void merge(state &a, int mx, int cnt){
	if (a.mx > mx) return;
	if (a.mx < mx) a.mx = mx, a.cnt = 0;
	a.cnt = add(a.cnt, cnt);
}
 
state dp[52][64][2];
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	int mx = *max_element(a.begin(), a.end());
	vector<vector<int>> cnt(n + 1, vector<int>(mx + 1));
	forn(i, n){
		cnt[i + 1] = cnt[i];
		++cnt[i + 1][a[i]];
	}
	forn(_, q){
		int l, r;
		cin >> l >> r;
		--l;
		memset(dp, -1, sizeof(dp));
		dp[0][0][0] = {0, 1};
		forn(i, mx + 1){
			int c = cnt[r][i] - cnt[l][i];
			int c2 = c * 1ll * (c - 1) / 2 % MOD;
			forn(val, 64) forn(fl, 2) if (dp[i][val][fl].cnt > 0){
				if (c > 0)
					merge(dp[i + 1][val ^ i][true], dp[i][val][fl].mx + c - 1, mul(dp[i][val][fl].cnt, c));
				if (c > 1)
					merge(dp[i + 1][val][true], dp[i][val][fl].mx + c - 2, mul(dp[i][val][fl].cnt, c2));
				merge(dp[i + 1][val][fl], dp[i][val][fl].mx + c, dp[i][val][fl].cnt);
			}
		}
		auto ans = dp[mx + 1][0][1];
		if (ans.cnt == -1)
			cout << -1 << '\n';
		else
			cout << ans.mx << ' ' << ans.cnt << '\n';
	}
}