Description

有一个四位数字密码锁，每一位可以显示 0~9，初始状态为 0000。 每一次操作只能把 某一位 向上或向下旋转一次（9 → 0、0 → 9 视为一次旋转），即一次操作只能把密码的 一位 加 1 或减 1（取模 10）。 给定目标密码 target（四位数字），以及若干 禁用密码 dead（这些密码一旦出现锁会立即报警，不能进入）。 请你计算从 0000 到达 target 所需的最少操作次数。如果无法到达（即所有可能的路径都要经过禁用密码），输出 -1。 目标密码本身可能是禁用密码。如果 target 本身在禁用列表中，则视为不可达，直接输出 -1。 初始密码 0000 也可能在禁用列表中，此时同样输出 -1。

Format

Input

第一行：目标密码，一个恰好四位的字符串（可能有前导 0），如 0234。 第二行：整数 n，表示禁用密码的数量 (0 ≤ n ≤ 1000)。 接下来 n 行：每行一个禁用密码，格式同上，均为四位字符串。

Output

输出一个整数：从 0000 到达 target 的最少操作次数；若不可达则输出 -1。

Samples

0202 
3
0201
0101 
0202 

-1

0202 
2
0201
0102
0101  

6