You are given a tree with $n$ nodes and $n-1$ edges that make all nodes connected. Each node $i$ is assigned a weight $a_i$.
Now you need to perform $m$ operations of two different types. One is to change the weight of a node. The other is to query the number of pairs $(x,y)$ $(1 \le x \le y \le n)$ in the entire tree such that the greatest common divisor of the weights of all nodes on the shortest path from node $x$ to node $y$ is $k$.
Input
The first line contains a single integer $T$ $(1\le T\le 8)$, representing the number of test cases.
For each test case, the first line contains two integers $n$ $(1\le n\le 10^4)$ and $m$ $(1\le m\le 10^4)$, representing the number of nodes and operations respectively.
The second line contains $n$ integers. The $i$-th integer $a_i$ $(1\le a_i\le 10^4)$ represents the initial weight of node $i$.
The third line contains $n-1$ integers. The $i$-th integer $p_{i+1}$ $(1\le p_{i+1}\le i)$ represents that there's an edge between node $i+1$ and node $p_{i+1}$.
The following $m$ lines describe the operations.
- $\texttt{0 u c}$: change the weight of node $u$ $(1\le u\le n)$ to $c$ $(1\le c\le 10^4)$;
- $\texttt{1 k}$: query the number of pairs $(x,y)$ $(1 \le x \le y \le n)$ in the entire tree such that the greatest common divisor of the weights of all nodes on the shortest path from node $x$ to node $y$ is $k$ $(1 \le k \le 10^4)$.
Output
For each query, output the answer in a single line.