Borya最近发现了一个大型电子显示屏。管理显示的计算机存储一些整数。该数字有 n 位十进制数字,显示屏显示该数字的编码版本,其中每个数字都使用英文字母表中的某个小写字母显示。
显示屏附近有一个图例,描述了数字的编码方式。对于每个数字位置 i 和每个数字 j,字符 c 是已知的,它在该位置对该数字进行编码。不同的数字可以具有相同的代码字符。
每秒数字增加 1。一秒后,当数字达到十进制数 n 9-s 表示的值时,会发出响亮的蜂鸣声。
安德鲁知道计算机中存储的号码。现在他想知道需要经过多少秒,Borya 才能明确说出显示器编码的原始数字是什么。假设 Borya 可以精确测量时间,并且编码的数字将在 Borya 开始观看显示屏的一秒后首先增加。
输入
输入数据包含多个测试用例。输入的第一行包含 t (1 ≤ t ≤ 100) — 测试用例的数量。
每个测试用例描述如下。描述的第一行包含 n (1 ≤ n ≤ 18) — 数字中的位数。第二行包含 n 个不带空格的十进制数字(但可能有前导零)——最初存储在显示计算机中的数字。以下 n 行每行包含 10 个字符。这些行中第 i 行的第 j 个字符是位置 i 中数字 j - 1 的代码字符,首先描述最高有效数字位置。
输出
对于每个测试用例,打印一个整数:直到 Borya 明确知道计算机显示屏上存储的初始数字是多少秒。不要打印前导零。
示例
输入 #1
3 2 42 abcdefghij jihgfedcba 2 42 aaaaaaaaaa aaaaaaaaaa 1 2 abcdabcdff
输出 #1
0 58 2