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