Ни на йоту больше
Начните с целого числа N_0, которое больше 0. Пусть N_1 будет количеством единиц в двоичной записи числа N_0. Например, если N_0 = 27, то N_1 = 4.
В общем случае, пусть N_i будет количеством единиц в двоичной записи числа N_{i-1}. Эта последовательность всегда будет сходиться к единице.
Для любого начального числа N_0, пусть K(N_0) будет минимальным i таким, что N_i равно единице. Например, если N_0 = 31, то N_0 = 5, N_{1} = 5, N_2 = 2, N_3 = 1, следовательно, K(31) = 3.
Дано множество последовательных чисел и значение X. Сколько чисел в этом множестве имеют значение K(...) равное X?
Входные данные
В файле данных будет несколько тестовых случаев. Каждый тестовый случай будет состоять из трех целых чисел в одной строке:
LO HI X
где LO и HI (1 ≤ LO ≤ HI ≤ 10^18) являются нижней и верхней границами диапазона целых чисел, а X (0 ≤ X ≤ 10) является целевым значением для K(...).
Файл данных заканчивается строкой с тремя 0.
Выходные данные
Для каждого тестового случая выведите строку с одним целым числом, представляющим количество целых чисел в диапазоне от LO до HI (включительно), которые имеют значение K(...) равное X в вводе.