# ACM MidAtlantic-2010

# Not One Bit More

Start with an integer, **N _{0}**, which is greater than

**0**. Let

**N**be the number of ones in the binary representation of

_{1}**N**. So, if

_{0}**N**=

_{0}**27**,

**N**=

_{1}**4**.

In general, let **N _{i}** be the number of ones in the binary representation of

**N**. This sequence will always converge to one.

_{i-1} For any starting number, **N _{0}**, let

**K**(

**N**) be the minimum

_{0}**i**such that

**N**is one. For example, if

_{i}**N**=

_{0}**31**, then

**N**=

_{0}**5**,

**N**=

_{1 }**5**,

**N**=

_{2}**2**,

**N**=

_{3}**1**, so

**K**(

**31**) =

**3**.

Given a range of consecutive numbers, and a value **X**, how many numbers in the range have a **K**(...) value equal to **X**?

**Input **

There will be several test cases in the data file. Each test case will consist of three integers on a single line:

**LO HI X**

where **LO** and **HI** (**1** ≤ **LO** ≤ **HI** ≤ **10 ^{18}**) are the lower and upper limits of a range of integers, and

**X**(

**0**≤

**X**≤

**10**) is the target value for

**K**(...).

The data file will end with a line with three **0**s.

**Output **

For each test case, output a line with a single integer, representing the number of integers in the range from **LO** to **HI** (inclusive) which have a **K**(...) value equal to **X** in the input.

31 31 3 31 31 1 27 31 1 27 31 2 1 4 1 1023 1025 1 1023 1025 2 0 0 0

1 0 0 3 2 1 1