OHANIGAME - Ohani And The Game

no tags 

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

hide comments
xpshekhar: 2015-12-30 23:34:51

irriated
compiled in 0s in ideone
and tle here

submission id : 15977104
pls check

shivam_15: 2015-11-11 08:45:57

@ Sushant Gupta: ans is 5 for 20

Aman Kumar: 2015-10-18 15:41:07

use only scanf printf something wrong with the judge

Last edit: 2015-10-24 11:13:32
utkarsha gaumat: 2015-10-13 19:43:32

tle

Alex Anderson: 2015-10-11 02:38:21

What's the point of having the input "maybe be a negative number, but it doesn't really matter" ?

Also... why even bother describing the game at all? Almost completely irrelevant.

2ND edit... Please choose the correct judge type next time. Ending with a newline should not result in WA.

Last edit: 2015-10-11 04:28:42
Sushant Gupta: 2015-09-26 09:23:55

for n = 20, the answer is 1 or 2 ?

saurajit: 2015-09-24 17:20:49

can the same divisor be taken twice?

adi_tri: 2015-09-24 15:03:11

some more tricky test cases please..


Added by:Raihat Zaman Neloy
Date:2015-09-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY