描述
Your company has just invented a new kind of number generator for generating huge random integers. It works in a really strange way.
Initially, there are many predefined rules. Each rule contains two parts, a single-digit d and a number k. A rule “d k” can be applied to any digit equals to d in a number s, and this digit will be substituted by k. Thus a new number s is born. For example, suppose s is 12315, and there is a rule “1 78”, then we can apply this rule to the first digit of s to obtain 782315, or to the forth one to obtain 123785. Notice that the number k of a rule can be empty (represented by a single character “e”), and applying this kind of rule to a digit is just as same as removing this digit from s.
Here comes the whole generating process:
1. At the beginning, let s be a single-digit number chosen from 0 to 9 (do not count this action as one step);
2. On each step, apply one of the rules to a digit of s to obtain a new s. Repeat this action for arbitrary times.
Unfortunately, you realize that there may be a critical flaw in this number generator -- it is too slow! Now you are going to prove the existence of this flaw by showing some concrete instances to your boss. You have already come up with a number s, and you need to write a program to determine the least number of steps to obtain it.
To simplify this problem, assume that any numbers may contain leading zeroes but these leading zeroes are taken into account during comparison. For instance, 96, 096, 0096 are different from each other.
输入
The first line contains an integer T (1 ≤ T ≤ 10) -- the number of test cases.
For each test case:
The first line contains an integer n, indicates the number of rules. 1 ≤ n ≤ 100.
Then follows n lines, each line contains a single-digit d and a number k, separated by a single space. 0 ≤ d ≤ 9. k is either a number only consists of digits (0 to 9) and its length is between 1 and 10, or empty (represented by a single character “e”).
The last line contains a number s. s only consists of digits (0 to 9) and its length is between 1 and 10.
输出
For each test case, output one integer in a single line -- the least number of steps to obtain s, or “-1” if s cannot be obtained within (less than or equal to) 88 888 888 steps.
样例输入
1
3
0 12315
1 78
3 e
12785
样例输出
3
