minions-approach

Minion's approach is Correct, if number of the positive integers less than or equal to N that are relatively prime to N, is prime or else Incorrect.
In other words, let Z be the number of integers K in the range 1 ≤ K ≤ N for which the greatest common divisor gcd(N,K) = 1. If Z is prime then Minion's Approach is Correct else it is Incorrect.

Given an integer N, your task is to check if a minions approach is Correct or Incorrect.

Input: First line contains T - number of test cases.
Each of next T lines contain an integer N.

Output: Print approach type of each N in a new line i.e. "Correct" or "Incorrect".

Constraints:   1 ≤ T ≤ 10   |   1 ≤ N ≤ 100000 

SAMPLE INPUT
4
2
3
4
5

SAMPLE OUTPUT
Incorrect
Correct
Correct
Incorrect

Explanation

For N=4, numbers ≤ 4 and relatively prime to 4 are 1 and 3. So there are 2 numbers that are relatively prime to 4. Since 2 is a prime. Approach is Correct.

For N=5, numbers ≤ 5 and relatively prime to 5 are 1,2,3 and 4. So there are 4 numbers that are relatively prime to 5. Since 4 is not a prime. Approach is Incorrect.

Difficulty: EASY

Starter code:

Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
from fractions import gcd
from math import sqrt
t=eval(input())
while t>0:
	t-=1
	n=eval(input())
	c=0
	for i in range(1,n+1):
		if gcd(i,n)==1:
			c+=1
	if c==1 or c==0:
		print("Incorrect")
		continue
	for i in range(2,int(sqrt(c))+1):
		if c%i==0:
			print("Incorrect")
			break
	else:
		print("Correct")


import math

noOfTestCases = int(input())

def isPrime(no):
	if(no == 1):
		return "Incorrect"
	
	start = 2
	
	while(start <= math.sqrt(no)):
		if(no%start == 0):
			return "Incorrect"
	return "Correct"
	
def gcd(n,k):
	start = 1
	gcd = 1
	while(start <= min(n,k)):
		if(n%start == 0 and k%start == 0):
		  gcd = start
		start += 1	
	return gcd		

def minionApproach(value):
	count = 0
	start = 1
	while(start <= value):
		if(gcd(start, value) == 1):
			count += 1
		start += 1
	print(isPrime(count))
	

for caseNo in range(1, noOfTestCases + 1):
	minionApproach(int(input()))


def gcd(a,b):
	A=a
	B=b
	if B==0:
		return A
	else:
		return gcd(B,A%B)

def is_prime(a):
	flag=1
	if a==1:
		return 0
	for i in range(2,a,1):
		if a%i==0:
			flag=0
			break
	if flag==1:
		return 1
	else:
		return 0

for _ in range(int(input())):
	x=int(input())
	c=0
	for r in range(1,x+1):
		if gcd(r,x)==1:
			c+=1
		else:
			pass
	if is_prime(c):
		print("Correct")
	else:
		print("Incorrect")
		


from fractions import gcd
t = eval(input())
for _ in range(t):
	n = eval(input())
	z = 0
	for i in range(1,n+1):
		if(gcd(n,i)==1):
			z+=1
	N = int(z**0.5)
	isp = True
	if(z==1):
		isp=False
	else:
	    for i in range(2,z):
	        if(z%i==0):
	            isp=False
	            break
	if(isp):
		print("Correct")
	else:
		print("Incorrect")
	


import math

noOfTestCases = int(input())

def isPrime(no):
	if(no == 1):
		return "Incorrect"
	
	start = 2
	
	while(start <= math.sqrt(no)):
		if(no%start == 0):
			return "Incorrect"
	return "Correct"
	
def gcd(n,k):
	start = 1
	gcd = 1
	while(start <= min(n,k)):
		if(n%start == 0 and k%start == 0):
		  gcd = start
		start += 1	
	return gcd		

def minionApproach(value):
	count = 0
	start = 1
	while(start <= value):
		if(gcd(start, value) == 1):
			count += 1
		start += 1
	print(isPrime(count))
	

for caseNo in range(1, noOfTestCases + 1):
	minionApproach(int(input()))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
from fractions import gcd
from math import sqrt
t=eval(input())
while t>0:
	t-=1
	n=eval(input())
	c=0
	for i in range(1,n+1):
		if gcd(i,n)==1:
			c+=1
	if c==1 or c==0:
		print("Incorrect")
		continue
	for i in range(2,int(sqrt(c))+1):
		if c%i==0:
			print("Incorrect")
			break
	else:
		print("Correct")