One day Ohani and her friend was playing a game. The rules of the game is given below:

1. Ohani Starts the game. Then the two player take turns.
2. At the starting of the game, Ohani and her friend together choose a number N.
3. They take the absolute value of N, N = |N| or, N = abs(N).
4. In one turn: a player chooses a divisor X of N where 1 < X <= N. Then he/she divides N by X. Then next player continues to do step 4 until N is not equal to 1.
5. The game ends when N becomes 1.
6. The player who can’t make his/her next move, looses the game. Both the player plays optimally.

Ohani and her friend was playing the game for a long time. So, they got bored. Then suddenly one interesting idea came to Ohani’s mind. She wants to choose maximum number of ways to get 1 from N such that no two way has a common number except 1 and N?

For explanation:

Suppose N = 20.

Two possible way to get 1 is: 20 → 10 → 5 → 1 and 20 → 5 → 1, both the way has number 5 in common.

But: 20 → 10 → 1 and 20 → 4 → 2 → 1 has no number common without 20 and 1.

So, now Ohani wants to know the number of ways such that no two way has common number except 1 and N. But Ohani is very weak in coding. So, she wants you to help.

Input

The first line of the input contains the number of testcases T (<= 100000).

Each of the next T lines contains a number N (|N| <= 1000000).

Output

For each testcase, output the desired answer. If it is impossible to reach 1, just print “Impossible”.

Example

Input:
3
1
2
3

Output:
0
1
1