You are given a tree with \(N\) nodes and \(N-1\) edges. Each node \(i\) of the tree is assigned a color \(A[i]\). Let \(c(x, y)\) be the array of colors encountered while traversing from node \(x\) to node \(y\) in the tree in the order.

Let \(f(x, y)\) represent the number of inversions in the array \(c(x, y)\).

You need to compute \(f(x, y) + f(y, x)\) for \(Q\) different queries.

• Inversions in an array \(arr\) is equal to the count of pairs \((i, j)\) such that \(i < j\) and \(arr[i] > arr[j]\).
• A tree is a graph with \(N\) nodes and \(N-1\) edges such that it is possible to travel from any node to any other node.

Input format

• First line of the input contains an integer \(T\), representing the number of test cases.
• The first line of each test case contains \(2\) space-separated integers \(N\), \(Q\) representing the number of nodes and the number of queries respectively.
• The next line of each test case contains \(N\) integers seperated by a space representing array \(A\), the array of colours.
• Next \(N-1\) lines of each test case contains \(2\) integers space-separated integers \(X, Y\) each \((X, Y)\), representing that there's an edge between node \(X\) to node \(Y\).
• The next \(Q\) lines of each test case contains \(2\) space-separated integers \(x, y\) each \((x, y)\) representing the queries.

Output format

For each query output the answer in a new line representing the value \(f(x, y) + f(y, x)\).

Constraints

• \(1 \leq T \leq 10^5 \)
• \(2 \leq N, Q \leq 10^5\)
• \(1 \leq A[i] \leq N \)
• \(1 \leq X, Y \leq N, X \neq Y\)
• \(1 \leq x, y \leq N, x \neq y\)
• It is guranteed that sum of \(N\), \(Q\) over all test cases does not exceed \(10^5\)