3076: Matrix

Matrices are square tables, containing integers in rows and columns. Do you know how to multiply matrices? The product of matrices $A$ and $B$ of size $n \times n$ is a matrix $C = AB$, such that
$$C(i, j) = \sum_{k = 1}^{n} A(i, k)\cdot B(k, j)$$
Here the brackets contain numbers of row and column, where the corresponding element of matrix is located.

One day, God Chai has been addicted to studying till midnight, after which he feels extremely hungry. Thus he turns to Coach Fang for some chocolates. But Coach Fang is a pretty cunning person, so that God Chai must figure out his question before getting chocolates.

The question is that, give $8$ types of matrices, an incomplete matrix sequence $A$ and a target matrix $m$. Initially, the matrix sequence $A$ consists of $n$ elements ranging from $0$ to $8$, in which $0$ means void. For every $0$ in $A$, God Chai need replace it with number $1 \sim 4$. There is no need to replace all $0$ with the same number. But eventually, the product of $n$ matrices in $A$ should equal to the target matrix $m$.

$8$ types of matrices are as following : 



Now please judge if it is possible to solve the question.

The first line contains an integer number T, the number of test cases.

For each test case :

The first line contains an integer $n$($1 \leq n \leq 10^{5}$), the number of matrix sequence $A$.

The second line contains $n$ integers $A_{i}$($0 \leq A_{i} \leq 8$), the serial number of matrices in $A$.

The third line contains an integer $m$($1 \leq m \leq 8$), the serial number of target matrix.

For each test case print“YES”(without quotes) if it is possible, and“NO”(without quotes) otherwise.

2
4
0 2 7 3
5
4
2 3 7 0
5

YES
NO