Problem Description

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.

2
8 6
2 1 5 6 7 2 3 4
1 2 2 4 4 1 7
1 2
0 2 2
1 2
1 5
0 7 4
1 2
3 5
1 2 3
1 1
1 1
0 1 6
1 2
1 3
1 6

3
9
1
17
4
2
2
1