Fouad、ACPC 评委和组织者们饿了，于是他们去了一家餐馆。这家餐馆制作串烧鸡肉块，每串鸡肉有 $N$ 块，其中第 $i$ 块鸡肉有一个整数 $A_i$，代表烹饪该块鸡肉所用的香料混合比例。从 Fouad 的角度来看，当一组连续鸡肉块的香料混合比例的最大公约数（GCD）恰好等于 $D$ 时，这组鸡肉块被认为是美味的。

由于 Fouad 想尝试串烧的许多子部分，他不断向评委提出查询，每个查询包含三个整数 $L$、$R$ 和 $D$，他想知道在范围 $A_L, A_{L+1}, \dots, A_R$ 内，有多少个连续子部分的香料混合比例的 GCD 等于 $D$；即满足 $gcd(A_i, A_{i+1}, \dots, A_j) = D$ 且 $L \le i \le j \le R$ 的所有数对 $(i, j)$ 的数量。

由于评委们想放松一下，不想做题只想吃饭，他们请求你帮他们解决这个问题。你能解决吗？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$ ($1 \le N \le 10^5, 1 \le Q \le 5 \cdot 10^4$)，其中 $N$ 是串烧中鸡肉块的数量，$Q$ 是 Fouad 将要提出的查询数量。

接下来一行包含 $N$ 个整数 $A_1, \dots, A_N$ ($1 \le A_i \le 10^6$)，其中 $A_i$ 代表烹饪第 $i$ 块鸡肉所用的香料混合比例。

随后有 $Q$ 行，每行包含三个空格分隔的整数 $L, R, D$ ($1 \le L \le R \le N, 1 \le D \le 10^6$)，表示查询。

输出格式

对于每个测试用例，每行输出一个查询的结果，即在给定范围 $[L, R]$ 内，香料混合比例的 GCD 等于 $D$ 的连续子部分的数量。

样例

输入 1

1
8 4
1 12 24 8 4 16 2 3
3 7 4
1 8 1
1 4 3
2 6 4

输出 1

6
14
0
9

说明

多个参数的最大公约数是根据以下方程递归计算的： $gcd(x_1, x_2, \dots, x_n) = gcd(gcd(x_1, \dots, x_{n-1}), x_n)$。