Домашнє завдання#1422
Школярі часто стикаються з різноманітними дивними задачами. Деякі з них, хоч і здаються безглуздими, вимагають багато часу для розв'язання. Наприклад, в одній зі шкіл було задано таку домашню задачу: подати натуральне число у вигляді суми степенів двох натуральних чисел. Спочатку це не виглядає складним. Однак, після того як перелічили всі варіанти, де хоча б одна з основ або хоча б один з показників дорівнює , кмітливі, але ліниві учні зрозуміли, що знаходження інших випадків вимагатиме перевірки великої кількості варіантів, а це залишає мало часу на відпочинок.
Тож вони вирішили заплатити розумну суму тому, хто зробить це завдання за них. Чому б не скористатися цією можливістю і не заробити трохи грошей, написавши програму, яка знаходить решту випадків?
У першому рядку задано натуральне число , 1 \leq N \leq 2000000000.
У першому рядку виведіть одне натуральне число — кількість різних способів подати у вигляді a^x + b^y, де a, b, x, y — натуральні числа, жодне з яких не дорівнює ; a \geq b, а якщо a = b, то x \geq y.
Далі виведіть рядків, у кожному з яких чотири числа a, x, b, y, розділені пробілами. Кожний рядок описує спосіб подати у заданій формі. Четвірки повинні бути впорядковані спочатку за зростанням , потім (якщо однакові) за , і якщо і рівні — за .
Приклад 1