Описанная ниже игра представляет собой классический пример теории комбинационных игр:

Два игрока начинают с полоской из n белых квадратиков, и совершают ходы по очереди.
На каждом ходу, игрок выбирает два следующих друг за другом квадрата и закрашивает их черным цветом.
Проигрывает тот игрок, который не может завершить свой ход.

• Если n = 1, возможных правильных ходов нет, таким образом первый игрок проигрывает автоматически.
• Если n = 2, возможен только один правильный ход, после которого второй игрок проигрывает.
• Если n = 3, возможны два варианта правильного хода, но обе ситуации приводят к проигрышу второго игрока.
• Если n = 4, возможны три варианта правильного хода для первого игрока, который может победить, если закрасит два средних квадрата.
• Если n = 5, возможны четыре варианта правильного хода для первого игрока (показаны ниже красным), однако независимо от выбора, второй игрок (синий) победит.

Таким образом, при 1 ≤ n ≤ 5, существуют 3 значения n, при которых первый игрок может свести результат к своей победе.
Аналогично, при 1 ≤ n ≤ 50, существуют 40 значений n, при которых первый игрок может свести результат к своей победе.

Если 1 ≤ n ≤ 1 000 000, то при скольких значениях n первый игрок может свести результат к своей победе?