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