Migrated from Lutece 622 吴神方程

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

最近吴神在研究一个方程$x^3-2^n\times x^2+n=0$，吴神发现了很多性质。为了纪念吴神的伟大贡献，学术界命名该方程为吴神方程。

现在设$x$为吴神方程最大的那个根，比如$n=2$时，$x=3.86619826\cdots$

现在给定$n$($1\leq n\leq 1000000$) ,求$\left \lfloor x^{987654321} \right \rfloor\ mod\ 100000000$, $\left \lfloor x \right \rfloor$代表下取整

Input

第一行有个整数$T$，代表数据组数（$T\leq 100$）

接下来有$T$行，每行有个整数$n$ ($1\leq n\leq 1000000$)

Output

输出$T$行，每行输出一个整数

Samples

3
1
2
3

24098476
76228863
85565262

Resources

UESTC Training for Math