StepJump C

题目描述

奶牛\(Liupin\)想跳\(N\)级阶梯，由于腿短，他一次只能跳\(1\)阶，\(2\)阶或\(3\)阶。

他已经跳到了顶端，求他跳跃的方案数量，由于答案可能很大你只需输出答案\(\mod 998244353\)后的值。

本题多测，共\(Q\)次询问。

输入格式

输入共\(Q+1\)行

第一行一个数字\(Q\)。

其后\(Q\)行，一行一个数字\(N\)。

输出格式

共\(Q\)行，一行一个答案\(Ans\)。

输入输出样例 #1

输入 #1

2
4
3

输出 #1

7
4

说明/提示

\(Q<10^5,N < 10^{18}\)