The school holiday has arrived... Some students have gone home, while others are being visited by old friends, making accommodation a problem. For example, if A and B are both students at the school, A is going home, and C is visiting B, but C does not know A. We assume that everyone can only sleep in the bed of someone they know directly. A possible solution would be for B to sleep in A's bed and for C to sleep in B's bed. In reality, the situation can be very complex; some people may know many students, and students at the school do not necessarily all know each other. We know there are a total of $n$ people, and we know whether each person is a student at the school, as well as whether each student at the school is going home. Determine if there exists a plan such that all students who are not going home and all visitors who have come to see them have a place to sleep.

Input

The first line contains an integer $T$, representing the number of test cases. For each test case, the first line contains an integer $n$, representing the total number of people involved. The next line contains $n$ integers, where the $i$-th integer indicates whether the $i$-th person is a student at the school ($0$ means no, $1$ means yes). The following line contains $n$ integers, where the $i$-th integer indicates whether the $i$-th person is going home ($0$ means not going home, $1$ means going home; note that if the $i$-th person is not a student at the school, this value is random and should be ignored after reading). The next $n$ lines each contain $n$ integers, where the $j$-th integer in the $i$-th line indicates whether person $i$ and person $j$ know each other ($1$ means they know each other, $0$ means they do not; the value for the $i$-th row and $i$-th column is $0$, but obviously, one can still sleep in their own bed). The relationship of knowing each other is mutual.

Output

For each test case, if a plan exists, output "^_^" (without quotes); otherwise, output "T_T" (without quotes). (Note that the output characters are half-width, with ASCII codes 94, 84, and 95 respectively.)

Constraints

• For 30% of the data, $1 \le n \le 12$.
• For 100% of the data, $1 \le n \le 50, 1 \le T \le 20$.

Examples

Input 1

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

Output 1

^_^