매우 긴 수식

당신은 수학 관련 챗봇을 개발하는 인공지능 회사의 소유주다. 평소에는 순조롭게 돌아가지만 오늘은 그렇지 않다. 인공지능 관련 기계가 모두 멈춰 버렸고, 설상가상으로 오늘은 유명한 연례 행사인 국제 황당 계산 대회(ICPC)가 열리는 날이다.

ICPC 참가자들은 정확한 산술식의 값을 알아내려고 회사의 서비스를 자주 이용한다. 올해도 다르지 않다. 대회 중에 이미 많은 질의가 들어왔지만 지금은 답할 수 없다.

각 질의는 정확히 $n$개의 문자로 이루어진 산술식의 정확한 값을 요구한다. 여기서 $n$은 홀수이며, 문자열은 다음 조건을 만족한다.

• 문자열은 숫자 0부터 9까지와 산술 연산 기호 '+', '-', '*', '/'로만 이루어진다.
• 홀수 번째 문자(1번째, 3번째, ..., $n$번째)는 숫자이고, 나머지 문자는 연산 기호다.
• '/' 기호 바로 뒤에 숫자 0이 오지 않는다.

예를 들어 '1*2/3+4-5', '0', '9/2'는 어떤 $n$에 대해 위 조건을 만족한다. 반면 '23-5', '-7', '5/0', '998244353'은 조건을 만족하지 않는다.

산술식의 값은 일반적인 연산자 우선순위를 따라 계산한다. 먼저 곱셈과 나눗셈을 왼쪽에서 오른쪽으로 모두 수행한다. 그다음 덧셈과 뺄셈을 왼쪽에서 오른쪽으로 수행한다.

위 조건을 만족하는 모든 식이 다음 질의로 나올 확률이 같다고 할 때, 결과값의 기댓값은 얼마인가?

첫 번째 줄에 테스트 케이스의 개수 $T$ ($1 \leq T \leq 2 \cdot 10^4$)가 주어진다.

이어지는 $T$개의 줄에는 각각 홀수 $n$ ($1 \leq n < 10^{18}$)이 하나씩 주어진다. $n$은 산술식의 길이다.

각 테스트 케이스마다 정수 $R$ ($0 \leq R < 998\,244\,353$)을 한 줄에 출력한다. 기댓값이 기약분수 $\frac{P}{Q}$이면, $P \equiv QR \pmod{998\,244\,353}$을 만족해야 한다. 어떤 $n$에 대해서도 기댓값은 유리수이며, 그러한 $R$은 항상 존재한다.

처음 세 테스트 케이스의 답은 각각 $\dfrac{9}{2}$, $\dfrac{170\,929}{21\,840}$, $\dfrac{25\,555\,213\,441}{2\,146\,435\,200}$이다.