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.