← 返回题目列表

Codeforces · 720/E

E. 密码

中文机器翻译题面 查看原题

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