Hey, ACRush and Jelly are playing a game ! Let take a look at its rule:

You are given a tree. Two players take turns cutting edges on a tree. Some nodes is on the "ground". When a player cuts an edge, all the edges that are no longer connected to the ground disappear. The player who can not take a move loses.

ACRush plays first. Both of them are very good players. If you know state of the tree they are playing with, can you guess who will win?

Input

Input consists of multiple test-cases. The first line contains one integer t - number of cases (0 < t <= 20). For each case, the input format is following. The first line contains one integer N (1 <= N <= 100000). The next line N integers s[i] (1 or 0). If s[i] is 1, the i-th node is on the ground. If s[i] is 0, the i-th node is not on the ground. Each line of the following N - 1 lines contains two integers u, v. They denote there is an edge between node u and node v (1 <= u,v <= N).
There is no blank line after each case.

Output

For each case, output who will win the game. If ACRush wins, output 1; otherwise, output 0 (Jelly wins).
There is no blank line after each case.

Example

Input:
1
4
0 0 0 1
1 2
2 3
2 4

Output:
1