#2084 ( N + N’) 는 소수인가?

111  1 s   128 MB  

Description

임의의 양의 정수 N이 있다고 할 경우 이 N을 뒤집은 수를 N'이라고 하자. (만약 N이 18223라면 N을 뒤집은 수 N'은 32281이다. ) N을 입력 받아 N과 N'을 더해서 그 결과가 소수이면 Prime 을 출력하고 만약 소수가 아니면 Not Prime 을 출력하는 프로그램을 작성하라.

Input

테스트 케이스의 수 T가 들어온다. (1 <= T <= 20)

그 다음 T만큼 정수 N이 들어온다. (1 <= N <= 10,000,000)(N은 0으로 시작하지 않는 정수이다.)

Output

각 테스트 케이스마다 (N+ N') 가 소수이면 Prime 을, 소수가 아니면 Not Prime 을 한 줄에 하나씩 출력한다.

Sample Input

Sample Output

2
172
3400
Prime
Not Prime

Source

동의대학교 멀티미디공학과 우영운(2013년 4월 23일)