eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Цифри

Цифри

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Для додатнього числа a визначимо функцію S(a), рівну сумі його цифр у системі числення з основою l. Крім того, нехай L(a) - мінімальне k, для якого S^k(a) не перевищує l-1. Потрібно знайти мінімальне a, таке що L(a)=N для заданого N і вивести його по модулю m.

Вхідні дані

N

m

l

0

N

10

^5

^{ }

1

m

10

^9

2

l

10

^9

Вхідний файл містить декілька тестів і завершується рядком "0 0 0". Кожен тест задано у окремому рядку, який містить трійку чисел , , (, , ).

Вихідні дані

Для кожного тесту виведіть його номер та мінімальне значення a по модулю m.

Приклад

Вхідні дані #1
0 1000 10
1 1000 10
0 0 0
Вихідні дані #1
Case 1: 1
Case 2: 10
Джерело ACM-ICPC Japan Alumni Group Spring Contest 2012 , Tokyo, Japan, 2012-04-15