E. Шифр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Боря увидел большое электронное табло. На табло зашифровано некоторое число. Само число состоит из n разрядов, каждый из которых записан с помощью маленькой латинской буквы.

Рядом с табло находится табличка, которая описывает схему шифрования. Так для каждого разряда i и цифры j известен символ c, которым она кодируется. При этом разным цифрам могут соответствовать одинаковые буквы.

Каждую секунду число, которое кодируется на табло, увеличивается на один. А через секунду после того, как все n цифр числа, зашифрованного на табло, оказываются равны девяти, табло издает очень громкий звук.

Андрей знает, какое число было зашифровано на табло в самом начале. Ему стало интересно, через сколько секунд Боря сможет точно определить это число. Считайте, что Боря абсолютно точно может замерять время, а также, что первый раз число на табло поменяется ровно через секунду после того, как Боря увидел табло.

Входные данные

В первой строке задано целое число t (1 ≤ t ≤ 100) — количество тестовых примеров. Описание каждого теста начинается с числа n (1 ≤ n ≤ 18) — количества символов в зашифрованном числе. В следующей строке записано n цифр без пробелов (возможно с ведущими нулями) — зашифрованное число. В следующих n строках записано по десять символов. Если j-й символ в строке i равен c, то цифра j - 1 в i-м разряде (более старшие разряды описаны раньше) кодируется буквой c.

Выходные данные

Для каждого тестового примера в отдельной строке выведите одно целое число без ведущих нулей — минимальное количество секунд, которое необходимо, чтобы расшифровать число.

Пример
Входные данные
3
2
42
abcdefghij
jihgfedcba
2
42
aaaaaaaaaa
aaaaaaaaaa
1
2
abcdabcdff
Выходные данные
0
58
2