Perfect Number

Source: beecrowd

Version: Phuoc Hung OJ Extended

Problem Statement

Given t positive integers, determine whether the sum of positive divisors strictly less than x equals x. Output the exact Portuguese wording for each value; 1 is not perfect.

Input

First t, followed by exactly t positive integers.

Output

For each integer x, print exactly x eh perfeito or x nao eh perfeito, with the numeric x substituted.

Subtasks

• Subtask 1 (20%): 1 ≤ t ≤ 5; 1 ≤ x ≤ 1000.

• Subtask 2 (30%): 1 ≤ t ≤ 10; 1 ≤ x ≤ 10^6.

• Subtask 3 (50%): 1 ≤ t ≤ 20; 1 ≤ x ≤ 10^8.

Examples

Example 1

Input:

3
6
5
28

Output:

6 eh perfeito
5 nao eh perfeito
28 eh perfeito

Explanation: Six and twenty-eight are perfect; five is not.

Example 2

Input:

1
1

Output:

1 nao eh perfeito

Explanation: One has no proper divisors.