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
| 31 | = | 3 | = | 30 × 3 | ≡ | 1 × 3 | = | 3 | ≡ | 3 (mod 7) |
| 32 | = | 9 | = | 31 × 3 | ≡ | 3 × 3 | = | 9 | ≡ | 2 (mod 7) |
| 33 | = | 27 | = | 32 × 3 | ≡ | 2 × 3 | = | 6 | ≡ | 6 (mod 7) |
| 34 | = | 81 | = | 33 × 3 | ≡ | 6 × 3 | = | 18 | ≡ | 4 (mod 7) |
| 35 | = | 243 | = | 34 × 3 | ≡ | 4 × 3 | = | 12 | ≡ | 5 (mod 7) |
| 36 | = | 729 | = | 35 × 3 | ≡ | 5 × 3 | = | 15 | ≡ | 1 (mod 7) |
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
Input: 3 6 7 9</p>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