지그재그

Zack의 Zergonomics Zegree는 상점에서 상품을 진열하는 최적의 방법이 지그재그 모양으로 쌓는 것이라고 가르쳤다.

Zack은 가게 진열대에 한 줄로 놓을 상자 $n$개를 진열해야 한다. 각 상자에는 피규어가 하나씩 들어 있다. 상자는 서로 위에 쌓을 수 있고, 모두 같은 모양이라 서로 구별되지 않는다. Zack은 스택의 개수를 정한 뒤, 각 스택이 비어 있지 않고 스택의 상자 수가 지그재그 수열을 이루도록 상자를 쌓아야 한다.

정확히 말하면, 왼쪽부터 1번부터 $s$번까지 번호를 붙인 스택이 $s$개($s \ge 1$) 있고, $i$번 스택에 $a_i$개의 상자가 있다고 하자. 다음 조건을 만족해야 한다.

• 각 $i$ ($1 \le i \le s$)에 대해 $a_i \ge 1$이다.
• $a_1 + a_2 + \dots + a_s = n$이다.
• 다음 중 하나 이상이 성립한다.
  • $a_1 < a_2 > a_3 < a_4 > \dots$
  • $a_1 > a_2 < a_3 > a_4 < \dots$

예를 들어 $n = 6$이면 그림 M.1과 같이 12가지 방법이 있다.

그림 M.1: $n = 6$일 때 가능한 12가지 방법 전부.

두 방법은 스택의 개수가 같고, 같은 위치의 스택마다 상자 수가 같을 때에만 같은 방법으로 본다.

Zack이 $n$개의 상자를 쌓는 서로 다른 방법의 수를 $998\,244\,353$으로 나눈 나머지를 구하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 300\,000$)가 주어진다. 이후 $t$개의 테스트 케이스가 각각 한 줄에 정수 $n$ ($1 \le n \le 300\,000$)으로 주어진다.

각 테스트 케이스마다 $n$개의 상자를 쌓는 서로 다른 방법의 수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.