Migrated from Lutece 1418 Endless Iteration

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

记$f(x)=2^x$。求$f^{(\infty)}(x)$在模$P$意义下的值。

Input

第一行一个整数$T$($T\leq 100000$),表示数据组数

接下来$T$行,每行一个整数$P$($T\leq 2000000000$),表示模数.

Output

共$T$行,每行一个整数,表示模$P$意义下的答案.

Samples

3
2
3
6

0
1
4

Note

$f^{(D)}(x)$表示$f(x)$迭代了$D$次

Resources

2016 UESTC Training for Math