33OJ
登录 注册

#P17775. 安和昴不是罪过

安和昴不是罪过

背景

『我不是骗子。』

题目描述

昴的乐队成员又开音趴去了,所以她只能自己花六七十打车回家。突然地,她想到了一段很美妙的旋律。

因为昴是鼓手,因而旋律可以被抽象为一个零一序列。昴觉得一段旋律是美妙的,当且仅当序列中极长零连续段的数量等于极长一连续段的数量。

  • 极长零连续段 [l,r][l,r] 定义为,aa 序列上 ll 至 rr 的所有元素均为零,且 ll 为序列左端点或 al−1=1a_{l-1}=1、rr 为序列右端点或 ar+1=1a_{r+1}=1,类似地定义极长一连续段。

但这段旋律太单调了,因此昴打算设计一段精彩的旋律。昴认为一个段长为 nn 的旋律序列 aa 是精彩的,当且仅当可以通过若干次下述消除操作将序列删空:

  • 选定 aa 的一个美妙的连续子段 [l,r][l,r],将其删除,并将 a[1:l−1]a[1:l-1] 和 a[r+1:n]a[r+1:n] 拼合起来得到新的序列。

现在昴好奇长为 nn 的精彩旋律个数,但昴到家了,所以这个问题交给了你,请你输出该值对 998244353998244353 取模的结果。

输入格式

第一行输入测试数据数 TT。

接下来 TT 行,每行一个整数表示该组测试数据的 nn。

输出格式

输出 TT 行,第 ii 行表示第 ii 组测试数据的答案。

5
1
2
3
4
5
0
2
4
10
22

提示

对所有数据,满足 1≤T≤1041\le T\le 10^4,1≤n≤10181\le n\le 10^{18}。


劝我袒露真心的是你,拦下我的还是你——

真是,受够了。