spoj
Състезание
Задача
F
Наименование
SPECIAL NUMBERS

Условие

ЗАДАЧА F. СПЕЦИАЛНИ ЧИСЛА
---
Когато изучавал признаците за делимост, Станчо много се впечатлил от тези за делимост на 3 и 9. Фактът, че едно число се дели на 9 тогава и само тогава, когато сборът от цифрите му се дели на 9, предизвиква у него нещо средно между изумление и страхопочитание. Подтикнат към нови алгебрични висини от това и необходимостта спешно да публикува няколко статии, той обобщил идеята, като дефинирал понятието K-специалнота:

Дефиниция: Едно цяло число се нарича K-специално тогава и само тогава, когато  се дели на K и сборът на цифрите в десетичният му запис също се дели на K.

Докато е много лесно да се каже колко числа в даден интервал са 3-специални или 9-специални, то за други стойности на K задачата съвсем не е проста. Ето защо, вие трябва да напишете програма, която Станчо да използва (без да я споменава в статията си), пресмятаща колко K-специални числа има в даден интервал.

На стандартния вход са дадени много заявки за пресмятане. Всяка от тях представлява ред с три цели числа – K (1 ≤  K ≤ 10^18), F (0 ≤  F ≤ 10^18) и T (F ≤  T ≤ 10^18).

За всяка заявка, вашата програма трябва да изведе на отделен ред на стандартния изход броя на K-специални числа в интервала от F до T включително.

Примерен вход:	
3 3 9
5 10 100
8 100 200
15 1000 2000	

Примерен изход:
3
2
1
15

« Предходна страница Решение Въпрос