Ним Вітгоффа

Двоє гравців змагаються в грі "Нім". На столі є 2 купки з n і k цукерками. Під час свого ходу гравець може забрати будь-яку кількість цукерок з однієї купки або однакову кількість з обох купок. Перемагає той, хто забере останню цукерку.

Визначте всі програшні позиції в цій грі, де загальна кількість цукерок n+k не перевищує max_sum.

Вхідні дані

У першому рядку подано одне число max_sum (1 ≤ max_sum ≤ 10^6).

Вихідні дані

На першому рядку виведіть кількість програшних позицій, а потім виведіть усі ці позиції, кожну на окремому рядку. Кожна позиція описується двома числами n і k (n ≤ k). Позиції повинні бути відсортовані за зростанням n, а при рівності — за зростанням k. Якщо програшних позицій більше 10^6, виведіть тільки перші 10^6.

Приклади