AOJ 6195 - Prime Test

Prime Test

Time Limit: 6000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 1811
64-bit integer IO format: %lld Java class name: Main

Submit Status Statistics

Font Size:

Description

Given a big integer number, you are required to find out whether it's a prime number.

Input

The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 2⁵⁴).

Output

For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.

Sample Input

2
5
10

Sample Output

Prime
2

Source

POJ Monthly