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

# 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