题目描述

定义如下函数：

$\red{pow(a,b)=a^b}$

$\red{F(x)=min\{Z|Z}$的因子数为$\red{pow(2,x)\}}$

求$\red{F(x)，}$答案对$\red{2334335669}$取模

输入格式

第一行输入一个整数$\red{T(1≤}$$\red{T≤}$$\red{1000)，}$代表样例数

接下去包含$\red{T}$行，每行一个整数，表示上述的$\red{x(0≤}$$\red{x≤}$$\red{5000)}$

输出格式

输出应包含$\red{T}$行，每行一个整数，表示上述答案$\red{F(x)}$对$\red{2334335669}$取模

样例

输入样例

4
1
2
3
4

输出样例

2
6
24
120