PROBLEM4  PRIMITIVEROOTS
Problem 4: PRIMITIVEROOTS
Introduction to Primitive Roots
a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n.
The number 3 is a primitive root modulo 7. because
Problem Statement
Given a number n as input you’ve to find the (product all the primitive roots of n) % n if n is prime.
Input
The first line consists of T the number of test cases followed by T lines. Each line consists of a prime number n.
Output
For each test case print the test case number followed by ‘:
’ followed by (product of all primitive roots of n) % n. If it is not a prime then print “NOTPRIME
”
Input Specifications
1 <= T <= 100
3 <= n <= 10000
Example
Sample Input
3 6 7 9
Sample Output
1:NOTPRIME 2:1 3:NOTPRIME
Description for test case #2:
The primitive roots of 7 are 3 and 5. The product % 7 = 15%7 =1
hide comments
Piyush Kumar:
20150616 08:54:40
Nice implementation of mathematics :) 

aqfaridi:
20140313 19:18:35
@J.A.R.V.I.S. nice comment .. 

saket diwakar:
20140313 19:18:35
don't deserve in classical....:P 

J.A.R.V.I.S.:
20140313 19:18:35
PROBLEM4 kids :D 

Aradhya:
20140313 19:18:35
for kids.. :D 

tainic:
20140313 19:18:35
This is just a math problem, shouldn't be here. 

mukesh tiwari:
20140313 19:18:35
Any particular reason for language restriction. Would it be possible to allow Haskell ? 
Added by:  cegprakash 
Date:  20110304 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Edited question from Kurukshetra 2011 