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