Два игрока играют в игру с двумя кучками камней. Они ходят по очереди. Если на текущий момент в первой кучке $a$ камней, а во второй - $b$ камней, то игрок в свой ход убирает $c\geq 0$ камней из первой кучки и $d\geq 0$ из второй таким образом, чтобы $ad-bc=\pm1$. Победит игрок, который первым полностью опустошит одну из кучек.

Заметим, что в игру возможно играть только в том случае, когда размеры кучек взаимно просты.

Состояние игры $(a, b)$ является выигрышной позицией, если следующий игрок может гарантированно победить при оптимальной игре. Определим $H(N)$ как количество выигрышных позиций $(a, b)$, где $\gcd(a,b)=1$, $a > 0$, $b > 0$ и $a+b \leq N$. Заметим, что порядок чисел имеет значение: например, $(2,1)$ и $(1,2)$ - это разные позиции.

Известно, что $H(4)=5$ и $H(100)=2043$.

Найдите $H(10^9)$.