An integer n is a 'perfect power' if it can be written as a^b for integers a >= 2 and b >= 2. Some numbers have more than one such representation (e.g. 64 = 2^6 = 4^3 = 8^2); to make the answer unique, always use the representation with the LARGEST possible exponent b (equivalently, the smallest possible base a).
Given n, output a^b (literally with a caret) for the representation with the largest exponent, or NONE if n is not a perfect power.
Input format
Line 1: a single integer n.
Output format
Either a string of the form a^b, or the string NONE.
Constraints
- 2 <= n <= 1000000000000