Nim Withoff
Two players are engaged in a game called "Nim." There are 2 piles, each containing n and k candies. During a player's turn, they can choose to remove any number of candies from one pile or the same number of candies from both piles. The player who removes the last candy wins the game.
Your task is to identify all losing positions in this game where the total number of candies, n+k, does not exceed max_sum.
Input
The input consists of a single integer max_sum (1 ≤ max_sum ≤ 10^6).
Output
First, output the number of losing positions. Then, list each losing position on a separate line. Each position is represented by two integers n and k (n ≤ k). The positions should be sorted in ascending order of n, and for ties, in ascending order of k. If there are more than 10^6 losing positions, only output the first 10^6.