Ані на йоту більше
Почніть з цілого числа 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 у вхідних даних.