t=int(input())
for ti in range(t):
	n=int(input())
	cnt=1
	i=2
	while i*i<=n:
		while n%i==0:
			n/=i
			cnt+=1
		if n!=1:
			cnt+=1
		i+=1
	if cnt%2==1:
		print('P')
	else:
		print('K')