e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ACM MidAtlantic-2010

Not One Bit More

Start with an integer, N0, which is greater than 0. Let N1 be the number of ones in the binary representation of N0. So, if N0 = 27, N1 = 4.

In general, let Ni be the number of ones in the binary representation of Ni-1. This sequence will always converge to one.

For any starting number, N0, let K(N0) be the minimum i such that Ni is one. For example, if N0 = 31, then N0 = 5, N1 = 5, N2 = 2, N3 = 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 (1LOHI1018) are the lower and upper limits of a range of integers, and X (0X10) is the target value for K(...).

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

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.

Time limit 1 second
Memory limit 64 MiB
Input example #1
31 31 3
31 31 1
27 31 1
27 31 2
1 4 1
1023 1025 1
1023 1025 2
0 0 0
Output example #1
1
0
0
3
2
1
1