Migrated from Lutece 1490 困难的数学题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个偶数n,求$f(n) ={{{{{n}^{n-1}}^{n-2}}^{....}}^{2}}^{1}$。也就是n的n-1的n-2的....的2的1次方。答案可能很大，只需输出答案对${2}^{32}$的模。

Input

输入包含多组数据. 第一行有一个整数$T (1\leq T\leq 100)$, 表示测试数据的组数. 对于每组数据:

输入一个整数 $n (1\leq n\leq 1,000,000)$并且 n mod 2 = 0。

Output

对于每组数据，输出一个整数

Samples

2
2
4

2
262144

Resources

每周一题 div3