Разбор добавил Анатолий Варивончик
Рассмотреть, какие мы получаем ответы при n от 1 до 19, и заметить, что при n >= 20 ответы мы получаем такой же как и при n от 0 до 9.(смотрим по модулю 10)