Задача 3E. Square coins ≡

Условие

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

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

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

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

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

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

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

Ограничения

8 ≤ n ≤ 10¹²

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

В примере дана стоимость монеты 72. Ей могут соответствовать три подходящих размера: 9² − 3² = 81 − 9 = 72, 11² − 7² = 121 − 49 = 72 и 19² − 17² = 361 − 289 = 72.

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

72

3
9 3
11 7
19 17