P17775 安和昴不是罪过

『我不是骗子。』

昴的乐队成员又开音趴去了，所以她只能自己花六七十打车回家。突然地，她想到了一段很美妙的旋律。 因为昴是鼓手，因而旋律可以被抽象为一个零一序列。昴觉得一段旋律是美妙的，当且仅当序列中极长零连续段的数量等于极长一连续段的数量。 * 极长零连续段 $[l,r]$ 定义为，$a$ 序列上 $l$ 至 $r$ 的所有元素均为零，且 $l$ 为序列左端点或 $a_{l-1}=1$、$r$ 为序列右端点或 $a_{r+1}=1$，类似地定义极长一连续段。 但这段旋律太单调了，因此昴打算设计一段精彩的旋律。昴认为一个段长为 $n$ 的旋律序列 $a$ 是精彩的，当且仅当可以通过若干次下述消除操作将序列删空： * 选定 $a$ 的一个美妙的连续子段 $[l,r]$，将其删除，并将 $a[1:l-1]$ 和 $a[r+1:n]$ 拼合起来得到新的序列。 现在昴好奇长为 $n$ 的精彩旋律个数，但昴到家了，所以这个问题交给了你，请你输出该值对 $998244353$ 取模的结果。

第一行输入测试数据数 $T$。 接下来 $T$ 行，每行一个整数表示该组测试数据的 $n$。

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。

对所有数据，满足 $1\le T\le 10^4$，$1\le n\le 10^{18}$。 --- 劝我袒露真心的是你，拦下我的还是你—— 真是，**受够了**。