[Wannafly冬令营2018Day7]斐波那契数列

内存限制：256 MB 时间限制：1000 ms

定义 $Fib_n$ 为斐波那契数列，$Fib_1=Fib_2=1$，$Fib_n=Fib_{n-1}+Fib_{n-2}~(n\geq 3)$

现在给定 $R$，你需要求 $\sum_{n=1}^{R}(Fib_n\&(Fib_{n}-1))$

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的值

第一行一个正整数 $T$ 表示数据组数 $(1\leq T\leq 10^4)$

接下来 $T$ 行，每行一个正整数 $R$ $(1\leq R\leq 10^{18})$

输出 $T$ 行，每行一个整数表示答案

C1689 [Wannafly冬令营2018Day7]斐波那契数列