Нещасливі числа#6218

Нещасливі числа

1 секунда
64 мегабайти
Середня

Числа теж мають почуття! Для будь-якого додатного цілого числа обчисліть суму квадратів його цифр і складіть їх разом. Отриманий результат піддайте такій же обробці. Число вважається щасливим, якщо після повторення цього процесу скінченну кількість разів сума дорівнює . Деякі щасливі числа потребують більше ітерацій, щоб дійти до , ніж інші, і це називається їхньою відстанню до щастя. Відстань до щастя для дорівнює . Відстань до щастя для дорівнює , оскільки 2^2 + 3^2 = 13, 1^2 + 3^2 = 10, і 1^2 + 0^2 = 1. Числа є нещасливими, якщо вони нескінченно далеко від щастя, оскільки застрягають у циклі. Дано нижню та верхню межі діапазону цілих чисел, визначте, скільки нещасливих чисел є в цьому діапазоні (включно).

Вхідні дані

У вхідних даних буде кілька тестових випадків. Кожен тестовий випадок складатиметься з двох додатних цілих чисел, lo та hi (0 < lo \le hi \le 10^{18}) на одному рядку, розділених пробілом. Вхідні дані завершуються двома .

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число в окремому рядку, яке вказує кількість нещасливих чисел між lo та hi (включно). Не виводьте зайвих пробілів і не розділяйте відповіді порожніми рядками.

Приклади

Приклад 1

Loading
Loading