Powerful numbers are positive integers that equal the sum of the $n$-th powers of their digits for some $n \in \mathbb{N}$. The smallest $n$ for which this property holds is called the order of the powerful number.

Consider, for example, the number 912985153. This is a powerful number of order 9 because $$9^9 + 1^9 + 2^9 + 9^9 + 8^9 + 5^9 + 1^9 + 5^9 + 3^9 = 912985153$$

Input

A positive integer.

Output

A line that indicates whether or not the given integer is a powerful number. In case the given number is a powerful number, the output must also indicate the order of the powerful number. The format of the output can be derived from the examples below.

Example

Input:

912985153

Output:

912985153 is a powerful number of order 9

Example

Input:

123456789

Output:

123456789 is not a powerful number

Resources

• Gardner M (1976). The Incredible Dr. Matrix. Charles Scribner's Sons, New York, 205-209.
• Deimel LE, Jones MT (1981). Finding pluperfect digital invariants: techniques, results and observations. Journal of Recreational Mathematics 14(2), 87-101.

Machtige getallen zijn natuurlijke getallen die gelijk zijn aan de som van de $n$-de machten van hun cijfers voor een zekere $n \in \mathbb{N}$. Het kleinste getal $n$ waarvoor deze eigenschap geldt noemen we de orde van het machtig getal.

Neem bijvoorbeeld 912985153. Dit is een machtig getal van orde 9 omdat geldt dat $$9^9 + 1^9 + 2^9 + 9^9 + 8^9 + 5^9 + 1^9 + 5^9 + 3^9 = 912985153$$

Invoer

Een natuurlijk getal.

Uitvoer

Een regel die aangeeft of het gegeven getal al dan niet een machtig getal is. Voor machtige getallen geeft de uitvoer ook aan wat de orde van het machtig getal is. Het formaat van de uitvoer kan je afleiden uit onderstaande voorbeelden.

Voorbeeld

Invoer:

912985153

Uitvoer:

912985153 is een machtig getal van orde 9

Voorbeeld

Invoer:

123456789

Uitvoer:

123456789 is geen machtig getal

Bronnen

• Gardner M (1976). The Incredible Dr. Matrix. Charles Scribner's Sons, New York, 205-209.
• Deimel LE, Jones MT (1981). Finding pluperfect digital invariants: techniques, results and observations. Journal of Recreational Mathematics 14(2), 87-101.