Задачи
Домашнее задание
Домашнее задание
Каких только странных задач не приходится решать школьникам! При этом некоторые из этих задач, являясь абсолютно бессмысленными, требуют достаточно много времени на решение. Так в одной из школ в качестве домашнего задания была дана следующая задача -- представить натуральное число в виде суммы степеней двух натуральных чисел. Казалось бы, ничего сложного. Однако, выписав в тетрадку все варианты, когда хотя бы одно из чисел, возводимых в степень, или хотя бы один из показателей равны \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}.
Входные данные #1
200
Выходные данные #1
2 10 2 10 2 14 2 2 2