Homework#1422
There are many peculiar problems schoolchildren have to solve. Some of them, while seemingly pointless, require a lot of time to solve. For example, in one school, the following problem was given as homework: express a natural number as the sum of powers of two natural numbers. At first, this does not seem complicated. However, after listing all the options where at least one of the bases or one of the exponents equals , clever but lazy students realized that finding other cases would require checking numerous possibilities, leaving little time for rest.
So, they decided to pay a reasonable fee for someone else to do their homework. Why not take this opportunity to earn some money by writing a program to find the remaining options?
The first line contains a natural number , 1 \leq N \leq 2000000000.
The first line should output a single natural number — the number of distinct ways to represent as a^x + b^y, where a, b, x, y are natural numbers, none of which equal ; a \geq b, and if a = b then x \geq y.
Then, lines should follow, each containing four numbers a, x, b, y, separated by spaces. Each line represents a way to write in the given form. The quadruples should be ordered first by increasing , then by if is equal, and by if and are equal.
Example 1