Problem Description

As the bell of $2024$ echoes, the legendary space-time gate opens again. This gate is a mysterious passage that connects two different digital worlds: binary and quaternary (base $4$), waiting for brave explorers.

In the binary world, a hero’s power is converted into the sum of the digits in the binary representation of the power value.

In the quaternary world, the conversion rule is similar: it becomes the sum of the digits in the base $4$ representation of the power value.

The condition to pass through this space-time gate is strict: if and only if the hero’s power in the binary world is equal to the hero’s power in the quaternary world, they can pass successfully.

The king chooses Xiaolan as the guide, leading heroes with power values from $1$ to $2024$ on this journey into the unknown. As Xiaolan’s assistant, your task is to help Xiaolan compute, among these $2024$ heroes, how many satisfy the condition to pass through the space-time gate.

Output Format

Output one integer in one line, representing the answer.

Hint

Translated by ChatGPT 5