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?

Node 4 is on the ground.

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 <i>N</i> (1 &lt;= <i>N</i> &lt;= 100000).
The next line <i>N</i> integers s[i] (1 or 0).
If s[i] is 1, the <i>i</i>-th node is on the ground.
If s[i] is 0, the <i>i</i>-th node is not on the ground.

Each line of the following <i>N</i> - 1 lines contains two integers u, v.
They denote there is an edge between node u and node v (1 &lt;= u,v &lt;= N).<br>

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