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