eolymp
bolt
Try our new interface for solving problems
Problems

Страусиная ферма

Страусиная ферма

Time limit 1 second
Memory limit 256 MiB

Как вы помните, Джонни работает в правительственных службах одной неизвестной страны. В свободное от государственных заданий время он разводит страусов на своей маленькой ферме.

На ферме есть n×m птиц. Джонни соорудил каждому страусу по загону, установив перегородки так, чтобы они образовывали прямоугольник из n строк и m столбцов. Тем самым образуется ровно n×m квадратных загонов 1×1. Обратите внимание: между соседними загонами он ставил ровно одну перегородку, а не две.

В один прекрасный осенний день заслуженный страус Чак, находившийся в нижнем левом загоне, почувствовал острую необходимость отправиться по важным и неотложным страусиным делам. Он начал пробивать себе путь на волю, ломая перегородки. Сначала он сломал правую перегородку и переместился загоном правее. Потом он сломал верхнюю перегородку и переместился вверх. Далее он прокладывал себе путь по такому же принципу: ломая попеременно то правую, то верхнюю перегородку, пока, наконец, не оказался на свободе.

Джонни, увидев разгром, учиненный Чаком, сильно расстроился. Но делать нечего — надо приводить все в порядок. Он отправил письмо на ближайшую лесопилку, указав, сколько у него осталось перегородок, но забыв при этом указать, сколько ему требуется.

Помогите работникам лесопилки: зная, сколько у Джонни осталось перегородок, определите, каких размеров могла быть ферма.

Input data

Количество перегородок x (1 x 10^9), оставшихся у Джонни.

Output data

В первой строке число возможных вариантов c размеров фермы Джонни. В последующих c строках выведите возможные варианты размеров фермы. В каждой строке следует вывести через пробел два целых числа — возможные значения n и m.

Обратите внимание: Джонни мог ошибиться при подсчете оставшихся перегородок, поэтому возможно, что не существует вариантов, подходящих под условие. В таком случае требуется вывести единственное число 0.

Examples

Input example #1
9
Output example #1
2
3 1
2 2