Танд A гэсэн бүхэл тоо өгөгдөнө. Уг A тоон дээр дараах үйлдлийг тодорхойлъё.

1. Одоогийн A тооны сүүлийн N цифрийн нийлбэрийг олно, хэрвээ оронгийн тоо N хүрэхгүй бол урдаа 0 ээр гүйцээсэн гэж үзнэ.
2. Нийлбэрийн нэгжийн орны цифрийг d гарсан гэж үзье.
3. d цифрийг тухайн A тооны баруун талд(төгсгөлд) нэмж бичнэ.
4. Үүссэн шинэ тооны сүүлчийн N цифрийг авч дараагийн үйлдэлд хэрэглэгдэх A тоо болгон авна.

Энэхүү үйлдлийг давтан хийснээр тоонуудын дараалал үүснэ.

Анхны A тоо дахин гарч ирэх хамгийн бага алхмын тоог ол.

Хэрэв өгөгдсөн M алхмын дотор анхны A дахин гарч ирэхгүй бол 0 хэвлэнэ.

Оролт:

A, N, M тоонууд хоосон зайгаар тусгаарлагдан өгөгдөнө.

Гаралт:

Анхны A тоо дахин гарч ирэх хамгийн бага алхмын тоог хэвлэнэ

Хэрэв M алхмын дотор давтагдахгүй бол 0 хэвлэнэ.

Хязгаарлалтууд:

• \(1 \leq A \leq 10^{18}\)
• \(1 \leq N \leq 2 \cdot 10^5\)
• \(1 \leq M \leq 10^{18}\)

Дэд бодлого

Жишээ:

Оролт-1

55555555 8 50

Гаралт-1

9

Оролт-2

11111111 8 100

Гаралт-2

0