PSYCHOT  Psycho34 (easy)
In the prime factorization of a number N, there's two kinds of powers.
Even powers, in red, are psychotic ones, and odd powers, in blue, are ordinary ones.
We'll say N a Psycho number if the count of even powers is
strictly greater than the count of odd powers, else an Ordinary number.
For example, if N = 67500 with prime factorization
67500 =
2^{2}
x
3^{3}
x
5^{4}
.
This number have 2
even powers
and 1
odd power.
Since 2>1, so the number 67500 is a Psycho Number.
Input
The first line of input contains an integer T, the number of test cases.
Each of the next T lines contains one integer N.
Output
For each test case, print if N is Psycho or Ordinary number.
Example
Input: 2 3 4 Output: Ordinary Number Psycho Number
Constraints
0 < T < 10^4 1 < N < 10^14
Time limit is ×2 my top speed with Python3 language, it could be not easy with slow languages.
O(N^.5 / log(N)) should give TLE even with fast languages. You are awaited to submit something between O(N^0.33 / log(N)) and O(N^0.25 / log(N)).
You can try before the quite similar "tutorial" problem : Psycho before.
@speed addicts : my top C timing is 0.02s. (TL updated 20170211 ; compiler changes)
hide comments
anonymous:
20180224 08:02:29
@Francky：I have passed this problem with a method whose time complexity is O(n^(1/3)/log(n)). But I have no idea about how to solve it in O(n^(1/4)/log(n)). Could you give me some hints? Thanks.


Sayak Haldar:
20150313 13:54:41
Yes, trial division(an approach between N1/3 and N1/4),sieve and good isprime function(rabin_miller with iteration upto 18 to eliminate all strong pseudoprimes) would pass it only with good observation(and heavy optimizations accordingly(I managed with scanf and printf)) But I am still unaware about the trick to solve it within 0.05 sec) 

Sayak Haldar:
20150309 15:27:48
Francky,Would you please tell me If I use Radin Miller Priamalty test how much iterations would suffice the job for numbers less than N<10^14 and is there any WA in the TLE solution in the solution id 13846476 ?


.:frUstrAteD:.:
20150305 22:50:44
Last edit: 20150305 22:51:10 

Vikneshwar E:
20150127 21:07:26
I have got Psychon solution accepted. But here I am getting wrong answer. Could someone please help me in figuring out the mistake.Submission ID 13534827


Vikneshwar E:
20150127 20:03:06
@Francky : Submission ID 13534827 . I am getting Wrong ans. Could you please help me to figure out where I am doing mistake ? Last edit: 20150127 21:10:05 

varun:
20141022 22:22:55
Can someone check my solution, submission id: 12699398.


XeRoN!X:
20140607 09:37:01
(easy) tag is fine considering the test cases. With N < 10^14 i am surprised how all solutions are incredibly fast.


[Lakshman]:
20140525 16:40:33
@Francky I think test cases need to be updated. Or we should think about n<=10^18.


fitcat:
20140523 07:22:43
@Francky: The test cases are not strong enough. My previous submissions incorrectly treated 202905198900 as an Ordinary number but got AC.

Added by:  Francky 
Date:  20140514 
Time limit:  1.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  PSYCHON 