You are tasked with solving a problem involving a tree structure consisting of $N$ nodes and $N-1$ edges. Each node in the tree is associated with a distinct value $A[i]$. That means all the values of the nodes are distinct.

Your objective is to process $Q$ queries, where each query provides three integers: $X$, $Y$, and $K$. Your goal is to determine the count of  nodes along the simple path from node $X$ to node $Y$ (inclusive) such that the values of the nodes are divisible by $K$.

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 the array $A$.
• Next $N-1$ lines of each test case contains $2$ space-separated integers $a, b$, representing that there's an edge between node $a$ and node $b$.
• The next $Q$ lines of each test case contains $3$ space-separated integers $X, Y, K$ representing the queries.

Output format

For each query output the answer in a new line representing the count of nodes divisible by $K$, on a path from Node $X$ to Node $Y$ inclusive.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N, Q \leq 10^5$
• $1 \leq A[i] \leq N$
• $1 \leq a, b, X, Y, K \leq N, a \neq b, X \neq Y$
• It is guaranteed that the sum of $N$, $Q$ over all test cases does not exceed $2*10^5$