eolymp
bolt
Try our new interface for solving problems
Problems

Ним Витхоффа

Ним Витхоффа

Time limit 2 seconds
Memory limit 64 MiB

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

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

Input data

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

Output data

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

Examples

Input example #1
20
Output example #1
4
1 2
3 5
4 7
6 10
Source III International Summer School Programming in Sevastopol 2012