Catwalk BrainF**k

난해한 프로그래밍 언어 BrainF**k은 +-][><,.의 여덟 가지 문자로만 작성되는 프로그래밍 언어이다.

• > : 포인터를 $1$ 증가시킨다.
• < : 포인터를 $1$ 감소시킨다.
• + : 포인터가 가리키는 값의 값을 $1$ 증가시킨다.
• - : 포인터가 가리키는 값의 값을 $1$ 감소시킨다.
• . : 포인터가 가리키는 값을 아스키 코드 문자로 출력한다.
• , : 하나의 문자를 입력받아, 포인터가 가리키는 값을 문자의 아스키 코드 값으로 덮어쓴다.
• [ : 포인터가 가리키는 바이트의 값이 $0$이라면 괄호 짝에 알맞은 ]로 이동한다.
• ] : 포인터가 가리키는 바이트의 값이 $0$이 아니면 괄호 짝에 알맞은 [로 이동한다.

[와 ]는 반복문의 시작과 끝을 나타내며, 이 둘이 올바르게 짝지어지지 않을 때만 컴파일에 실패한다.

고양이가 키보드 위를 걷는다. 고양이가 한 걸음을 내디딜 때마다 +-][><,. 중 무작위 한 글자를 화면에 입력하게 된다.

정수 $N$이 주어질 때, 고양이가 정확히 $N$걸음을 걸어 만든 길이 $N$의 문자열이 BrainF**k 코드로 컴파일될 확률을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$

각 테스트 케이스마다 한 줄에 답을 출력한다.

해당 테스트 케이스의 확률을 기약분수 $\cfrac{p}{q}$로 나타내자. $q$는 $998\,244\,353$의 배수가 아니다. $q^{-1}$을 법 $998\,244\,353$에서의 $q$의 곱셈 역원이라 할 때,

을 $0$ 이상 $998\,244\,353$ 미만의 정수로 출력한다.

• $1 \le T \le 200\,000$.
• $1 \le N \le 100\,000$.