该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

什么是树？
单个节点是树。
设有n（n为任意正整数）棵树，那么用一个新节点作为这些树根节点的父亲，这个结构也是树，这些根节点是新节点的儿子。
没有父亲的节点被称为“根”，没有儿子的节点被称为“叶子”。
特别的，如果每个非叶子节点都恰好有两个儿子节点，这个结构就被称为二叉树，此时这两个儿子节点是不同的，被称为左儿子和右儿子。
线段树是一类特殊的二叉树，其定义如下：
其中每个节点都代表一个正整数区间[l,r]，如果l=r，那么它是叶子。
根节点代表[1,n]。
设某非叶子节点代表的区间为[l,r]，m=(l+r)/2（向下取整）。
那么它的左儿子代表[l,m]，右儿子代表[m+1,r]。
在线段树上定位区间就是指，对于一段区间l,r，在线段树上找到最少的节点，使得这些节点所表示区间的并集为[l,r]。

Description

现在有一棵线段树，根节点表示区间[1,2^n]。
现在从1<=l<=r<=2^n的所有区间[l,r]中等概率选出一个区间在这棵线段树上进行定位，求定位到的节点的数量的期望值。

Format

Input

第一行一个整数T(T<=10)，表示测试数据组数。
接下来T行，每行一个整数n(n<=10^1000000)，注意这里的n可能包含前导0。

Output

按照输入顺序，对于每组输入数据，输出答案乘(2^n)(2^n+1)/2 mod 998244353。

Sample 1

Input

3

Output

65

Limitation

1s, 512MB for each test case.

Source

Vijos Original