Homework
Students often encounter peculiar problems to solve, some of which, despite being seemingly pointless, demand considerable time and effort. For example, at one school, students were tasked with expressing a natural number as the sum of powers of two natural numbers. Initially, this might appear straightforward. However, after listing all possibilities where at least one base or one exponent is equal to 1, the clever yet lazy students realized that finding additional solutions would require examining numerous cases, leaving them little time to relax.
Thus, they decided to pay a reasonable fee to have someone else complete the assignment. Why not seize the opportunity to earn some money by developing a program that identifies these solutions?
Input
The first line contains a single natural number N, where 1 ≤ N ≤ 2000000000.
Output
The first line should output a single natural number K — the number of distinct ways to express the number N in the form a^x + b^y, where a, b, x, and y are natural numbers, none of which are equal to 1. Additionally, a should be greater than or equal to b, and if a equals b, then x should be greater than or equal to y.
Following this, K lines should be printed, each containing four numbers a, x, b, y, separated by spaces and ending with a newline. These represent the ways to express the number N in the specified form. The quadruples should be ordered by increasing a, and in the case of equal a, by b, and if both a and b are equal, by x.