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