Regions in Burlandia form a graph with (n) vertices and (n-1) edges, and there is exactly one path between any two vertices. Formally, the regions form a tree. Each region has a friendliness value (a_i). There are (q) queries. In each query, a pair of friends located in different regions is given. They want to know how many subsegments of the path between these regions are hospitable . It is known that in Burlandia there are two criteria for evaluating relationships — XOR and sum. A subsegment of the path, containing some vertices lying on the path from region (x) to region (y), is called hospitable if it is non-empty and the sum of friendliness values on this subsegment does not exceed their XOR. More formally, for each query you are given two vertices (x) and (y) ((x \neq y)). Consider the shortest path from vertex (x) to vertex (y) in the tree. Let the vertices (v_1, v_2, \ldots, v_k) form this path, where (v_1 = x), (v_k = y). You need to find the number of subsegments of this path for which the following condition holds: () a_{v_{l}} \oplus a_{v_{l+1}} \oplus \ldots \oplus a_{v_{r}} \geq (a_{v_{l}} + a_{v_{l+1}} + \ldots + a_{v_{r}}), () where (1 \leq l \leq r \leq k) — the boundaries of the subsegment of vertices on the path from (x) to (y). Each test consists of multiple test cases. The first line contains a single integer (t) ((1 \leq t \leq 10^4)) — the number of test cases. Then the descriptions of the test cases follow. The first line of each test case contains integers (n) ((2 \leq n \leq 10^5)) — the number of vertices in the tree, and (q) ((1 \leq q \leq 10^5)) — the number of queries. The second line contains an array of (n) non-negative integers — the friendliness values of the regions ((0 \leq a_i \lt 2^{20})). The next (n - 1) lines describe the edges of the tree: each line contains integers (u, v) ((1 \leq u, v \leq n))