一个无脑的 GF 做法。

设 $n$ 的答案为 $f_n$。

显然我们每次要先取下最后一个环才能进行后面的操作。

而且取下前 $n$ 个环的答案和加上 $n$ 个环的答案相同。

于是我们每次先取下 $n-2$ 个环，再取最后一个，再装上 $n-2$ 个环，转化为 $f_{n-1}$ 的情况。

$$f_n = f_{n - 1} + 2f_{n - 2} + 1,n\ge 2$$

$f_1 = 1, f_0 = 0$。

显然没有这么简单，因为 $n\le 10^5$，要写高精。

列举前若干项后发现似乎有 $f_n = 2f_{n-1} + [2\not|n]$

考虑证明。 $f_1 = 2f_0 + 1$，当 $n>1$ 时，

$2|n$，$f_n = f_{n-1} + 2f_{n-2}+1 = f_{n-1}+(f_{n-1}-1)+1$

$2\not|n$，$f_n = f_{n-1} + 2f_{n-2}+1 = f_{n-1}+f_{n-1}+1$

于是可以估算位数，汉诺塔 $h_n = 2h_{n-1}+1\ge f_n$，且 $h_n = 2^n-1$，

则位数约为 $B = \lg(2^{10^5})\approx 3\times 10^4$。

朴素递推高精 $\mathcal O(mnB)$，时间无法承受。

所以我们尝试求通项。

$$\begin{aligned} F(x) &= f_0x^0 + f_1x^1 + f_2x^2\cdots \\ 2xF(x) &= 2f_0x^1 + 2f_1x^2 + 2f_2x^3\cdots \\ (1-2x)F(x) &= x^1 + x^3 + x^5\cdots \\ x^2(1-2x)F(x) &= x^3 + x^5 + x^7\cdots \\ (1-x^2)(1-2x)F(x) &= x \\ \end{aligned}$$$$F(x) = \dfrac{x}{(1-x)(1+x)(1-2x)}$$

猜测其为 $\dfrac{a}{1-x}$，$\dfrac{b}{1+x}$ 和 $\dfrac{c}{1-2x}$ 的和，$a,b,c$ 是常数。

于是可以解得 $a = -\dfrac{1}{2},b = -\dfrac{1}{6}, c = \dfrac{2}{3}$。

$$\begin{aligned} F(x) &= \dfrac{a}{1-x} + \dfrac{b}{1+x} + \dfrac{c}{1-2x} \\ &= \sum_{n\ge 0}-\dfrac{1}{2}x^n - \dfrac{1}{6}(-1)^nx^n + \dfrac{2}{3}2^nx^n \end{aligned}$$$$f_n = \dfrac{-3-(-1)^n+2^{n+2}}{6}$$

现在要算 $2^{n+2}$。可以直接用 NTT 倍增算。

时间 $\mathcal{O}(mB\log B\log n)$。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

const int N = 200001;
const int p = 998244353;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
	do x = x * 10 + ch - 48, ch = getchar(); while(ch >= '0' && ch <= '9');
	return x * f;
}

inline int fastpow(int a,int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * a % p;
		a = 1ll * a * a % p;
		b >>= 1;
	}
	return res;
}

int r[N];

void NTT(int *a,int N) {
	for(int i = 0;i < N;i++) if(r[i] > i) std::swap(a[i],a[r[i]]);
	for(int n = 2, m = 1;n <= N;m = n, n <<= 1) {
		int g1 = fastpow(3,(p - 1) / n);
		for(int l = 0;l < N;l += n) {
			int g = 1;
			for(int i = l;i < l + m;i++) {
				int t1 = a[i], t2 = 1ll * a[i + m] * g % p;
				a[i] = (t1 + t2) % p;
				a[i + m] = (t1 - t2 + p) % p;
				g = 1ll * g * g1 % p;
			}
		}
	}
	return;
}

void INTT(int *a,int N) {
	NTT(a,N), std::reverse(a + 1,a + N);
	int iN = fastpow(N,p - 2);
	for(int i = 0;i < N;i++) a[i] = 1ll * a[i] * iN % p;
	return;
}

int a[N],b[N];

void Mul(int *x,int *y,int &n,int m) {
	int N = 1, l = -1; while(N <= n + m) N <<= 1, l++;
	for(int i = 0;i < N;i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l);
	for(int i = 0;i < n;i++) a[i] = x[i];
	for(int i = 0;i < m;i++) b[i] = y[i];
	for(int i = n;i < N;i++) a[i] = 0;
	for(int i = m;i < N;i++) b[i] = 0;
	NTT(a,N), NTT(b,N);
	for(int i = 0;i < N;i++) a[i] = 1ll * a[i] * b[i] % p;
	INTT(a,N); int v = 0; n = n + m;
	for(int i = 0;i < n;i++) {
		v += a[i];
		x[i] = v % 10, v /= 10;
		if(v && i == n - 1) n++;
	}
	while(n > 1 && !x[n - 1]) n--;
	return;
}

void Add(int *a,int n,int d) {
	int x = 0; a[0] += d;
	for(int i = 0;i < n;i++) {
		a[i] += x;
		if(a[i] < 0) a[i] += 10, x--;
		else if(a[i] > 9) a[i] -= 10, x++;
	}
}

void Div(int *a,int n,int d) {
	int x = 0;
	for(int i = n - 1;i >= 0;i--) {
		x = x * 10 + a[i];
		a[i] = x / d, x %= d;
	}
}

void print(int *a,int l) {
	while(l && !a[l]) l--;
	for(int i = l;i >= 0;i--) std::putchar(a[i] + 48);
	return;
}

int f[N],l,t[N],tl;

void Solve() {
	int n = read();
	for(int i = 1;i < N;i++) f[i] = t[i] = 0;
	f[0] = 1, t[0] = 2, l = tl = 1;
	int m = n + 2;
	while(m) {
		if(m & 1) Mul(f,t,l,tl);
		Mul(t,t,tl,tl);
		m >>= 1;
	}
	Add(f,l,-3 + ((n & 1) ? 1 : -1));
	Div(f,l,6);
	print(f,l), std::putchar('\n');
	return;
}

int main() {
	int m = read();
	while(m--) Solve();
	return 0;
}