CF720E.Cipher

Borya has recently found a big electronic display. The computer that manages the display stores some integer number. The number has n decimal digits, the display shows the encoded version of the number, where each digit is shown using some lowercase letter of the English alphabet.

There is a legend near the display, that describes how the number is encoded. For each digit position i and each digit j the character c is known, that encodes this digit at this position. Different digits can have the same code characters.

Each second the number is increased by 1. And one second after a moment when the number reaches the value that is represented as n 9-s in decimal notation, the loud beep sounds.

Andrew knows the number that is stored in the computer. Now he wants to know how many seconds must pass until Borya can definitely tell what was the original number encoded by the display. Assume that Borya can precisely measure time, and that the encoded number will first be increased exactly one second after Borya started watching at the display.

鲍里亚最近发现了一个大型电子显示屏。管理该显示屏的计算机中存储着某个整数。该数有 $n$ 位十进制数字，显示屏显示的是该数的编码版本，其中每一位数字均用英文字母表中的某个小写字母表示。

显示屏旁有一段说明，描述了该数字的编码方式：对每一位位置 $i$（从左至右编号，$1 \le i \le n$）以及每一个数字 $j$（$0 \le j \le 9$），均已知一个字符 $c$，表示数字 $j$ 在第 $i$ 位上所对应的编码字符。不同数字可以对应相同的编码字符。

每过一秒，该数字增加 $1$。当数字达到由 $n$ 个 $9$ 组成的十进制数（即 $10^n - 1$）后，再过一秒，便会响起一声响亮的蜂鸣声。

安德鲁知道计算机中存储的原始数字。现在他想知道：从鲍里亚开始观察显示屏起，至少需经过多少秒，鲍里亚才能确定无疑地推断出最初被显示屏编码的原始数字？假设鲍里亚能精确测量时间，且显示屏上显示的编码数字恰好在鲍里亚开始观察后的下一秒开始第一次递增。

Input data contains multiple test cases. The first line of input contains t (1 ≤ t ≤ 100) — the number of test cases.

Each test case is described as follows. The first line of the description contains n (1 ≤ n ≤ 18) — the number of digits in the number. The second line contains n decimal digits without spaces (but possibly with leading zeroes) — the number initially stored in the display computer. The following n lines contain 10 characters each. The j-th character of the i-th of these lines is the code character for a digit j - 1 in position i, most significant digit positions are described first.

输入数据包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例的描述如下：描述的第一行包含一个整数 $n$（$1 \le n \le 18$），表示该数字的位数；第二行包含 $n$ 个十进制数字（无空格，但可能含有前导零），即显示器中初始存储的数字。接下来的 $n$ 行每行包含 10 个字符。其中，第 $i$ 行的第 $j$ 个字符（$j$ 从 1 开始计数）表示在第 $i$ 位（从最高位开始描述）上数字 $j-1$ 所对应的编码字符。

For each test case print an integer: the number of seconds until Borya definitely knows what was the initial number stored on the display of the computer. Do not print leading zeroes.

对于每个测试用例，输出一个整数：Borya 确定知道计算机显示屏上初始数字所需的秒数。不要输出前导零。