Prime Number

Source: beecrowd

Version: Phuoc Hung OJ Extended

Problem Statement

Given X>1, determine whether X is prime. The PHOJ Extended edition handles one X from the original multiple-case input, preserving the original Portuguese output messages.

Input

One integer X.

Output

Print exactly "X eh primo" if prime, or "X nao eh primo" otherwise.

Subtasks

• Subtask 1 (20%): 2≤X≤100.
• Subtask 2 (30%): 2≤X≤100000.
• Subtask 3 (50%): 2≤X≤10000000.

Examples

Example 1

Input

7

Output

7 eh primo

Explanation

Seven has no divisor from two through its square root.

Example 2

Input

21

Output

21 nao eh primo

Explanation

Twenty-one is divisible by three.