Perfect, abundant or deficient

Problem

A number theory club sorts numbers by the sum of their proper divisors (all divisors except the number itself). If the sum equals the number it is PERFECT (6 = 1 + 2 + 3), if it is larger it is ABUNDANT, and if it is smaller it is DEFICIENT.

Write static long sumOfProperDivisors(int n) that only loops up to √n, and use it to label each number.

Input, output and limits

Input: The first line has an integer t. The next t lines each have one integer n.
Output: t lines, each PERFECT, ABUNDANT or DEFICIENT.
Constraints: 1 ≤ t ≤ 100
1 ≤ n ≤ 10^9

Examples

Example

Input

Output

PERFECT
ABUNDANT
DEFICIENT

6: 1+2+3 = 6. 12: 1+2+3+4+6 = 16. 8: 1+2+4 = 7.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Divisors come in pairs: if d divides n, so does n / d. Loop d from 2 while d * d <= n.

Hint 2

Add both d and n / d, but only once when they are equal.

Hint 3

Start the sum at 1 for n > 1 (1 is always a proper divisor), and return 0 for n = 1.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Methods problems

Problem

Input, output and limits

Examples

Hints

More Methods problems