You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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