Saruman's Level Up

Time limit1sMemory limit128 MB

Summary
For each N up to 10^16, count how many integers i in [1, N] have a binary digit sum that is a multiple of 3.
Level

Hard8 of 10

Topics
Dynamic programming, Bit manipulation, Math, Combinatorics
Solved
No attempts yet

Problem

Saruman's army of orcs and other dark minions mine coal and harvest lumber from the land surrounding his mighty tower every day for NN consecutive days. On day number ii, Saruman either spends resources on mining and harvesting, or on raising the level (that is, the height) of his tower. He raises his tower's level by exactly one unit only on days where the binary representation of ii contains a number of 1's that is an exact multiple of 3. The initial level of his tower on day 0 is zero.

For example, Saruman raises his tower's level on day 7 (binary 111), then on day 11 (binary 1011), and then on day 13, day 14, day 19, and so on.

Saruman would like to forecast the level of his tower after NN days. Can you write a program to help?

Input

The input contains multiple test cases, each on a single line. Each test case consists of a single positive integer NN (N<1016N < 10^{16}), as described above. The input ends at end of file (EOF).

Output

For each test case, output one line in the format Day N: Level = L, where NN is the given input and LL is the level of the tower after NN days.

Examples2

  1. Example 1

    Input
    2
19
64
    Expected output
    Day 2: Level = 0
Day 19: Level = 5
Day 64: Level = 21

  2. Example 2

    Input
    1
7
11
13
14
    Expected output
    Day 1: Level = 0
Day 7: Level = 1
Day 11: Level = 2
Day 13: Level = 3
Day 14: Level = 4