You are given a tree consisting of \(N\) nodes, where the \(i^{th}\) node has a value \(A_i\) assigned to it.

You can do the following operation any number of times. In an operation, you can :

• Select a node \(i \;(1 \le i \le N)\) and set \(A_i = \left \lfloor{\frac{A_i}{2}}\right \rfloor \).

Find the minimum number of operations to be performed so that the bitwise AND of the values present in any two adjacent nodes of the tree is zero.

Input format

• The first line of input contains an integer \(N\) denoting the number of nodes in the tree.
• The second line contains \(N\) integers \(A_1, A_2,\dots, A_N\), denoting the values assigned to the nodes.
• \(N-1\) lines follow. The \(i^{th}\) line contains two integers \(X_i, Y_i\) denoting a edge between the nodes \(X_i,Y_i\).It is guaranteed that the nodes and edges form a tree.

Output format
For each query, print the minimum number of operations to be performed so that the bitwise AND of the values present in any two adjacent nodes of the tree is zero.

Constraints