Parity of the number of divisors P24818

Write a program that reads a sequence of natural numbers and, for each one, tells if its number of divisors is even or odd.

For instance, 18 has 6 divisors (1, 2, 3, 6, 9 and 18), and 100 has 9 (1, 2, 4, 5, 10, 20, 25, 50 and ‍100).

Input

Input consists of a sequence of strictly positive natural numbers.

Output

Print each given number followed by “even” or “odd”, as required.

Observation

The trivial algorithm to solve this exercise is too slow. The fastest algorithm uses the square root. Try to find an intermediate solution.