Description

According to some books, one of God’s failed attempts at creation went like this:

On the first day, God created a basic element of the world, called "yuan" (pinyin).

On the second day, God created a new element, called $\alpha$. $\alpha$ is defined as a set composed of "yuan". It is easy to see that there are exactly two distinct $\alpha$.

On the third day, God created another new element, called $\beta$. $\beta$ is defined as a set composed of $\alpha$. It is easy to see that there are four distinct $\beta$.

On the fourth day, God created a new element, $\gamma$. $\gamma$ is defined as a set of $\beta$. Clearly, there are $16$ distinct $\gamma$.

If this continues, the fifth kind of element will have $65536$ types, and the sixth kind will have $2^{65536}$ types. This will be an astronomical number.

However, God did not anticipate how fast the number of element types would grow. He wanted to enrich the world’s elements, so day after day, year after year, he kept creating new elements…

Not long after, when God created the last kind of element $\theta$, he found that there were so many elements that the world’s capacity was insufficient to bear them. So that day, God destroyed the world.

To this day, God still remembers that failed act of creation. Now he wants to ask you: how many distinct elements of type $\theta$ are there?

God thinks this number may be too huge to represent, so you only need to report it modulo $p$.

You may assume that from $\alpha$ to $\theta$, God created elements for $10^9$ steps, or $10^{18}$ steps, or simply $\infty$ steps.

In short:

Define $a_0=1,a_n=2^{a_{n-1}}$. It can be proved that $b_n=a_n\bmod p$ becomes constant after some index; find that value.

Input Format

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains one positive integer $p$, the modulus.

Output Format

Output $T$ lines, each containing one positive integer, which is the answer modulo $p$.

3
2
3
6

0
1
4

Hint

For $100\%$ of the testdata, $T\le 10^3$, $p\le 10^7$.

Translated by ChatGPT 5