Background

摆满香蕉的小岛

蕉蕉蕉蕉

睡蕉小猴的爱巢

蕉蕉蕉蕉

吃完香蕉就睡觉

蕉蕉蕉蕉

快快乐乐没烦恼

蕉蕉蕉蕉

睡蕉小猴真是好

蕉蕉蕉蕉

幸福美满没烦恼

Description

小张拥有一名游戏角色，他初始有五次普攻段数，每普攻一次消耗一次普攻次数，每次普攻后有50%概率额外获得一次普攻次数，假设他一次性会把普攻用完（额外获得的普攻次数也会用掉）那么他普攻总数为n(n>=5)的概率是多少。

Format

Input

第一行输入一个整数 T 表示数据组数。

每组数据输入一个整数 n 表示角色的普攻总数，保证 5 <= n <= 100000

Output

每行一个整数表示角色普攻 n 次的概率，如果答案可以表示成 $\frac{P}{Q}$ 的形式,则输出 $\frac{P}{Q}\%998244353$。

Samples

1
5

967049217

Limitation

1s，1024MB