Недавно Боря увидел большое электронное табло. На табло зашифровано некоторое число. Само число состоит из n разрядов, каждый из которых записан с помощью маленькой латинской буквы.
Рядом с табло находится табличка, которая описывает схему шифрования. Так для каждого разряда i и цифры j известен символ c, которым она кодируется. При этом разным цифрам могут соответствовать одинаковые буквы.
Каждую секунду число, которое кодируется на табло, увеличивается на один. А через секунду после того, как все n цифр числа, зашифрованного на табло, оказываются равны девяти, табло издает очень громкий звук.
Андрей знает, какое число было зашифровано на табло в самом начале. Ему стало интересно, через сколько секунд Боря сможет точно определить это число. Считайте, что Боря абсолютно точно может замерять время, а также, что первый раз число на табло поменяется ровно через секунду после того, как Боря увидел табло.
Выходные данные
Для каждого тестового примера в отдельной строке выведите одно целое число без ведущих нулей — минимальное количество секунд, которое необходимо, чтобы расшифровать число.