Challenge: Prime Checker

Lab Python Intermediate 20 points

Write a function is_prime(n) that returns True if n is a prime number and False otherwise. A prime is a whole number above 1 that only divides by 1 and itself (2, 3, 5, 7, 11…).

Then read numbers and print the result for each one.

Input

A count k, then k lines with one number each.

Output

For each number: <n> is prime or <n> is not prime.

Example

Input

Output

2 is prime
15 is not prime
17 is prime
1 is not prime
97 is prime

Sample input available Sample output available

Editor

Python

Hints

Numbers below 2 are not prime.

Try dividing by every number from 2 upwards; if any divides exactly, it's not prime.

You only need to try up to the square root: range(2, int(n ** 0.5) + 1).

Solution explanation

The function returns False as soon as it finds a divisor. If the loop finishes without one, the number is prime.

Show solution

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            return False
    return True


for _ in range(int(input())):
    n = int(input())
    print(n, "is prime" if is_prime(n) else "is not prime")

Output

Answer