Problem2449--CF1744a - Number Replacement

2449: CF1744a - Number Replacement

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description


题意:

给定一个数组和一个字符串,每次选择数组中的一个数和字符串中对应的一个字符,把数组中所有的该数字都替换成该字符,求能否将数组变成该字符串。


An integer array a1,a2,…,ana1,a2,…,an is being transformed into an array of lowercase English letters using the following prodecure:

While there is at least one number in the array:

  • Choose any number xx from the array aa, and any letter of the English alphabet yy.
  • Replace all occurrences of number xx with the letter yy.

For example, if we initially had an array a=[2,3,2,4,1]a=[2,3,2,4,1], then we could transform it the following way:

  • Choose the number 22 and the letter c. After that a=[c,3,c,4,1]a=[c,3,c,4,1].
  • Choose the number 33 and the letter a. After that a=[c,a,c,4,1]a=[c,a,c,4,1].
  • Choose the number 44 and the letter t. After that a=[c,a,c,t,1]a=[c,a,c,t,1].
  • Choose the number 11 and the letter a. After that a=[c,a,c,t,a]a=[c,a,c,t,a].

After the transformation all letters are united into a string, in our example we get the string "cacta".

Having the array aa and the string ss determine if the string ss could be got from the array aa after the described transformation?

Input

The first line contains a single integer tt (1≤t≤103(1≤t≤103) — the number of test cases.

Then the description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤501≤n≤50) — the length of the array aa and the string ss.

The second line of each test case contains exactly nn integers: a1,a2,…,ana1,a2,…,an (1≤ai≤501≤ai≤50) — the elements of the array aa.

The third line of each test case contains a string ss of length nn, consisting of lowercase English letters.

Output

For each test case, output "YES", if we can get the string ss from the array aa, and "NO" otherwise. You can output each letter in any case.

Sample Input Copy

7
5
2 3 2 4 1
cacta
1
50
a
2
11 22
ab
4
1 2 2 1
aaab
5
1 2 3 2 1
aaaaa
6
1 10 2 9 3 8
azzfdb
7
1 2 3 4 1 1 2
abababb

Sample Output Copy

YES
YES
YES
NO
YES
YES
NO

HINT

Note

The first test case corresponds to the sample described in the statement.

In the second test case we can choose the number 5050 and the letter a.

In the third test case we can choose the number 1111 and the letter a, after that a=[a,22]a=[a,22]. Then we choose the number 2222 and the letter b and get a=[a,b]a=[a,b].

In the fifth test case we can change all numbers one by one to the letter a.

Source/Category