OHANIGAME - Ohani And The Game
One day Ohani and her friend was playing a game. The rules of the game is given below:
- Ohani Starts the game. Then the two player take turns.
- At the starting of the game, Ohani and her friend together choose a number N.
- They take the absolute value of N, N = |N| or, N = abs(N).
- 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.
- The game ends when N becomes 1.
- 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
|
|
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" ?
|
|
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 |