Are you familiar with the data structure known as a red-black tree? In this problem, we will consider trees with red or black vertices, but don't worry—if you have heard of the aforementioned structure, it is best to quickly forget about it.

You are given a tree (a connected undirected graph without cycles) in which each vertex is painted one of two colors: red or black. The operation you can perform is to choose two vertices $v$ and $u$ connected by an edge and repaint $v$ with the color that $u$ is painted with.

Your task is to determine whether it is possible to obtain a given final configuration of colors from an initial configuration after some (possibly empty) sequence of operations.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^5$), representing the number of test cases.

The descriptions of the test cases follow. Each test case description begins with a line containing a single integer $n$ ($1 \le n \le 10^5$), representing the number of vertices in the tree.

The next line contains a string consisting of $n$ characters, each of which is 0 or 1. If the $i$-th character is 0, then the $i$-th vertex is initially painted red. If the $i$-th character is 1, then the $i$-th vertex is initially painted black.

The next line contains a string consisting of $n$ characters, each of which is 0 or 1, which describes in the same way whether each vertex should be red or black after performing the operations, where 0 also denotes red and 1 denotes black.

The next $n-1$ lines each contain two integers. The $j$-th of these lines contains integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le n; a_j \neq b_j$), indicating that vertices $a_j$ and $b_j$ are connected by an edge. You may assume that the given sequence of edges describes a valid tree.

The sum of $n$ over all test cases does not exceed $10^6$.

Output

The output should contain $t$ lines. If in the $k$-th test case it is possible to bring the tree to the desired state, the $k$-th line should contain the single word TAK. Otherwise, it should contain the single word NIE.

Examples

Input 1

3
4
1011
1100
1 2
2 3
2 4
2
10
10
1 2
2
10
01
1 2

Output 1

TAK
TAK
NIE

Note

Explanation of the example: In the first test case, we can first repaint the third vertex with the color of the second vertex, and then repaint the fourth vertex with the color of the second vertex. In this way, the last remaining vertex of the black color is the first vertex. It is therefore sufficient to now repaint the second vertex with the color of the first vertex. After these three operations, all vertex colors match the given final configuration.

In the second test case, we do not need to perform any operations – both vertices already have the correct color initially.

In the third test case, it is not possible to swap the colors of the vertices.