Домашнє завдання
Яких лише дивних задач не приходиться розв'язувати школярам! При цьому деякі з цих задач, будучи абсолютно безсмисленими, вимагають достатньо багато часу на розв'язання. Так у одній зі шкіл в якості домашнього завдання була задано наступну задачу – подати натуральне число у вигляді суми степенів двох натуральних чисел. Здавалось би, нічого складного. Проте, виписавши у зошит всі варіанти, коли хоча б одне з чисел, які підносяться до степені, або хоча б один з показників рівні 1, розумні, але ліниві школярі зрозуміли, що для того, щоб знайти інші варіанти, їм прийдеться перебрати дуже багато випадків і про відпочинок у найближчий час можна забути.
Тоді вони вирішили за помірну оплату замовити виконання домашнього завдання. Чому б Вам не заробити трохи грошей, написавши програму, яка знайде інші варіанти?
Вхідні дані
У першому рядку одне натуральне число N, 1 ≤ N ≤ 2000000000.
Вихідні дані
У першому рядку одне натуральне число K – кількість різних способів подання числа N у вигляді a^x+b^y таких, що a, b, x, y – натуральні числа, жодне з них не рівне 1, a ≥ b і, якщо a = b, то x ≥ y.
Далі K рядків по чотири числа a, x, b, y через пропуск, кожен з яких завершується переходом на новий рядок, – способи подання числа N у заданому вигляді. Ці четвірки чисел впорядковані між собою за зростанням a, а у випадку рівності a – по b, у випадку рівності a та b по x.