本题没有可用的提交语言。

Description

Omer is a mathematician who loves programming and the orange trees, when the office hours end he loves playing with his beautiful orange tree.

This orange tree consists of $n$ oranges numbered from $1$ to $n$, connected by $n-1$ bidirectional branches such that all oranges are connected between them by some sequence of branches. Also this orange tree is rooted in the orange $1$, and each orange has a weight $w_{i}$ $(1 < w_i <= n)$ where all $w_{i}$ are different, note that $w$ is a permutation of length $n$.

While playing with his orange tree, Omer asks himself some questions of the following form:

Given $u, a, b$ calculate the value $\sum_{i=a}^b f(u, i)$ where $f(u, i) = $ number of oranges with weight divisible by $i$ in the subtree rooted at orange $u$.

As he is very busy taking care of his children, he needs you to help him with his orange tree and to answer all his questions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 1000)$. The description of the test cases follows.

The first line consists in two integers $n, q$ $(2 \leq n, q \leq 2 \cdot 10^{5})$ — the number of oranges and the number of questions, respectively.

The second line contains a permutation of length $n$, $w_{1}, w_{2}, ... w_{n}$ — the weights of the oranges.

Then follows $n-1$ lines, each one consisting in two integers $u_{i}, v_{i}$ $(1 \leq u_{i}, v_{i} \leq n)$ — meaning that there is a branch between the oranges $u$ and $v$.

Finally follows $q$ lines, each one consisting in three integers $u_{i}, a_{i}, b_{i}$ $(1 \leq u_{i} \leq n ; 1 \leq a_{i} \leq b_{i} \leq n)$ — the questions asked by Omer.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $2 \cdot 10^{5}$.

Output

For each testcase, output $q$ integers — the answer to the questions.

2
5 4
1 5 3 4 2
2 1
2 4
3 5
3 2
1 2 4
2 3 5
1 1 5
3 2 2
2 6
2 1
1 2
1 1 1
1 1 2
1 2 2
2 1 2
2 1 1
2 2 2

4 3 10 1 
2 3 1 1 1 0

Note

—

Problem idea: danx

Problem preparation: danx

Ocurrences: Advanced 8