该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P1039 The nflsM Tokens (EASY) (Fib3 Queue 2)

Problem Background

The NFLS (Nasty Fluffy Lost School) Mathematics & Logic & Life Club is holding a ceremony! There’s a kind of tokens, called the nflsM Tokens, in this ceremony.

AppOfficer (as a student of the school again), again get the tokens easily. But Cui2010 can’t get them by himself! So he asks AppOfficer to give him some, even if he won’t get much of them this way.

AppOfficer asks him to answer a question. Can you help him answer?

Problem Statement

Define \(F3(n)=F3(n-1)+F3(n-2)+F3(n-3)\ (n>3)\) with \(F3(0)=0,F3(1)=F3(2)=1\).

Given \(t\) queries. For each query, get the value of \(F3(x)\), modulo \(998244353\).

Input

\(t\)
\(\text{Query}_1\)
\(\text{Query}_2\)
\(\text{Query}_3\)
\(\ \ \ \ \ \vdots\)
\(\text{Query}_t\)

For each query, there’s an integer \(x\) in one line.

Output

For each query, print \(F3(x)\) in a line.

Constraints

• \(1 \le t \le 5000\).
• \(1 \le x \le 10^{12}\).
• All values in input are integers.

Samples

Input 1

10
1
2
3
5
7
9
10
12
13
14

Output 1

1
1
2
7
24
81
149
504
927
1705

The \(F3\) sequence: \(\left\{(0),1,1,2,4,7,13,24,44,81,149,274,504,927,1705,\cdots\right\}\)

From the sequence we can get the answer.