eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ним Витхоффа

Ним Витхоффа

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Двое играют в игру "Ним". Есть 2 кучки из n и k конфет. Игрок в свой ход может вытянуть произвольное количество конфет из одной кучки или вытянуть одинаковое количество из обеих кучек. Выигрывает тот, кто взял последнюю конфетку.

Найдите все проигрышные позиции в этой игре, в которых суммарное количество конфет n+k не превосходит max_sum.

Входные данные

В первой строке записано единственное число max_sum (1max_sum10^6).

Выходные данные

В первой строке выведите количество проигрышных позиций, затем выведите все эти позиции на отдельной строке. Позиция описывается двумя числами n и k (nk). Позиции выводите по возрастанию n, а при равенстве по возрастанию k. Если проигрышныхпозиций больше 10^6, то выведите только первые 10^6.

Пример

Входные данные #1
20
Выходные данные #1
4
1 2
3 5
4 7
6 10
Источник III Международная Летняя школа программирования 2012 г. Севастополь