Задача E. Square coins

Автор:Anton Karabanov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

"Сенсационная находка!", "Археологи обнаружили древнюю цивилизацию!", "Ученые поражены развитием древних технологий!" — такими заголовками пестрели новости. Обнаруженные под толщей песка пустыни Сахары артефакты действительно поражали: совершенные приборы и механизмы, манускрипты и пергаменты с непонятными записями, предметы искусства и быта - всё указывало на существовавшую когда-то в этом регионе развитую цивилизацию. Ученые нацелились на долгую и кропотливую работу.

Нумизматов же, конечно заинтересовала денежная система Древнесахарцев (так окрестили обнаруженную цивилизацию). Были найдены золотые монеты разного размера, все исключительно квадратной формы и с квадратным отверстием посередине. Что интересно - все размеры (и сторон монет, и сторон отверстий) были нечетными числами. Было высказано предположение, что стоимость монеты соответствовала её площади: так на монете размером 5 с отверстием 1 было отчеканено 24 точки, на монете размером 5 с отверстием 3 нашлось 16 точек, на монете размером 3 с отверстием 1 отчётливо видно 8 точек. Всё указывало на то, что стоимость монеты равна разности квадратов стороны монеты и стороны отверстия: 52 − 12 = 24, 52 − 32 = 16, 32 − 12 = 8.

По данной стоимости монеты определите все её возможные размеры.

Формат входных данных

Входные данные содержат целое число n — стоимость монеты. Гарантируется, что n кратно восьми.

Формат выходных данных

В первой строке выведите целое число k — количество различных возможных размеров монет. В следующих k строках выведите по два числа: размер стороны монеты и размер отверстия. Записи упорядочите по возрастанию сторон монет.

Ограничения

8 ≤ n ≤ 1012

Пояснение к примеру

В примере дана стоимость монеты 72. Ей могут соответствовать три подходящих размера: 92 − 32 = 81 − 9 = 72, 112 − 72 = 121 − 49 = 72 и 192 − 172 = 361 − 289 = 72.

Примеры тестов

Стандартный вход Стандартный выход
1
72
3
9 3
11 7
19 17

0.169s 0.027s 17