for _ in range(int(input())):
    n = int(input())
    print(1 + (n == 1) if n <= 3 else (n + 2) // 3)

for _ in range(int(input())):
	n = int(input())
	p = [i + 1 for i in range(n)]
	print(n)
	for i in range(n):
		print(*p)
		if i < n - 1:
			p[i], p[i + 1] = p[i + 1], p[i]

INF = 2 * 10**9

for _ in range(int(input())):
	m = int(input())
	a = [[int(x) for x in input().split()] for i in range(2)]
	su = [[-INF for j in range(m + 1)] for i in range(2)]
	for i in range(2):
		for j in range(m - 1, -1, -1):
			su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1))
	pr = a[0][0] - 1
	ans = INF
	for j in range(m):
		jj = j & 1
		ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1))
		pr = max(pr, a[jj ^ 1][j] - 2 * j - 1)
		ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2))
		if j < m - 1:
			pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2)
	print(ans + 2 * m)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> dp(n + 1), ans(n + 1);
  dp[0] = 1;
  for (int mn = 0; mn + k <= n; mn += k++) {
    vector<int> sum(k);
    for (int i = mn; i <= n; ++i) {
      int cur = dp[i];
      dp[i] = sum[i % k];
      (sum[i % k] += cur) %= MOD;
      (ans[i] += dp[i]) %= MOD;
    }
  }
  for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}

#include<bits/stdc++.h>

using namespace std;     
const int K = 18;

struct node
{
    long long sum, pref, suff, ans;
    
    node(const node& l, const node& r)
    {                                                                                          
        sum = l.sum + r.sum;
        pref = max(l.pref, l.sum + r.pref);
        suff = max(r.suff, r.sum + l.suff);
        ans = max(max(l.ans, r.ans), l.suff + r.pref);
    }

    node(int x)
    {
        sum = x;
        pref = suff = ans = max(x, 0);
    }

    node() {};
};

int a[1 << K];
vector<node> tree[2 << K];  

void build(int v, int l, int r)
{
    tree[v].resize(r - l);
    if(l == r - 1)
    {
        tree[v][0] = node(a[l]);  
    }
    else
    {
        int m = (l + r) / 2;
        build(v * 2 + 1, l, m);
        build(v * 2 + 2, m, r);
        for(int i = 0; i < m - l; i++)
        {
            tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);
            tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);    
        }
    }
}

int main()
{            
    int n;
    scanf("%d", &n);
    int m = (1 << n);
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &a[i]);
    }
    build(0, 0, m);
    int q;
    scanf("%d", &q);
    int cur = 0;
    for(int i = 0; i < q; i++)
    {
        int x;
        scanf("%d", &x);
        cur ^= (1 << x);
        printf("%lld\n", tree[0][cur].ans);
    }
}

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;   
const int N = 2043;

int dp[N][N];

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   

int sub(int x, int y)
{
    return add(x, -y);
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}

void precalc()
{
    dp[1][1] = 1;
    for(int i = 1; i < N - 1; i++)
        for(int j = 1; j <= i; j++)
        {
            dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
            dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
        }
}

int solve(int n, int m, int k)
{
    int way1 = (m / 2) + (m % 2);
    int curA = n;
    int ans = 0;
    int ways_chosen = way1;
    int ways_other = binpow(m, n - 1);
    int invm = inv(m);
    for(int i = 1; i <= k; i++)
    {
        ans = add(ans, mul(mul(curA, dp[k][i]), mul(ways_chosen, ways_other)));
        curA = mul(curA, sub(n, i));
        ways_chosen = mul(way1, ways_chosen);
        ways_other = mul(ways_other, invm);
    }  
    return ans;
}   

int main()
{
    int t;
    cin >> t;
    precalc();
    for(int i = 0; i < t; i++)
    {
        int n, m, k;
        cin >> n >> m >> k;
        cout << solve(n, m, k) << endl;
    }
}