Задача C. Задачи для Фибоначчи ≡

Условие

Леонардо Пизанский размышляет над следующей задачей: сколько чисел среди первых n членов его знаменитой последовательности чисел Фибоначчи оканчиваются на цифру d?

Для определенности будем считать, что нумерация чисел начинается с единицы, то есть:

F(1) = 1

F(2) = 1

F(n) = F(n - 1) + F(n - 2)

Формат входных данных

Первая строка входного файла содержит натуральное число n, вторая — цифру d.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно неотрицательное целое число — количество подходящих членов последовательности.

Ограничения

1 ≤ n ≤ 10¹⁸

0 ≤ d ≤ 9

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 10⁵, получат не менее 40 баллов.

Пояснение к примеру

В примере дано n = 20 и d = 4. Среди первых двадцати чисел Фибоначчи на цифру 4 оканчиваются три: F(9) = 34, F(12) = 144 и F(18) = 2584.

Примеры тестов

20
4

3