311189: CF1946F. Nobody is needed

F. Nobody is neededtime limit per test6 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Oleg received a permutation $a$ of length $n$ as a birthday present.

Oleg's friend Nechipor asks Oleg $q$ questions, each question is characterized by two numbers $l$ and $r$, in response to the question Oleg must say the number of sets of indices $(t_1, t_2, \ldots, t_k)$ of any length $k \ge 1$ such that:

• $l \le t_i \le r$ for each $i$ from $1$ to $k$.
• $t_i < t_{i+1}$ for each $i$ from $1$ to $k-1$.
• $a_{t_{i+1}}$ is divisible by $a_{t_i}$ for each $i$ from $1$ to $k-1$.

Help Oleg and answer all of Nechipor's questions.

Input

Each test consists of several sets of input data. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of sets of input data. The description of the sets of input data follows.

The first line of each set of input data contains two integers $n$ and $q$ ($1 \le n, q \le 10^6$) — the length of the permutation and the number of Nechipor's questions.

The second line of each set of input data contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the permutation $a$ itself.

In each of the next $q$ lines of each set of input data, there are two integers $l$ and $r$ ($1 \le l \le r \le n$) — the next question of Nechipor.

It is guaranteed that the sum of the values of $n$ and the sum of the values of $q$ over all test cases does not exceed $10^6$.

Output

For each set of input data, output the answers to all of Nechipor's questions.

ExampleInput

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

Output

20 15 18 12 5 5 1 3
1
2 3 2
27

Note

All suitable arrays in the first set of input data: ($1$), ($2$), ($3$), ($4$), ($5$), ($6$), ($7$), ($8$), ($1, 3$), ($1, 6$), ($1, 7$), ($1, 6, 7$), ($2, 3$), ($2, 4$), ($2, 5$), ($2, 6$), ($2, 7$), ($2, 8$), ($2, 6, 7$), ($6, 7$).

All suitable arrays in the fourth set of input data: ($1$), ($2$), ($3$), ($4$), ($5$), ($6$), ($7$), ($8$), ($1, 2$), ($1, 3$), ($1, 4$), ($1, 5$), ($1, 6$), ($1, 7$), ($1, 8$), ($1, 2, 4$), ($1, 2, 6$), ($1, 2, 8$), ($1, 2, 4, 8$), ($1, 3, 6$), ($1, 4, 8$), ($2, 4$), ($2, 6$), ($2, 8$), ($2, 4, 8$), ($3, 6$), ($4, 8$).

题目大意：
Oleg 收到了一个长度为 n 的排列 a 作为生日礼物。他的朋友 Nechipor 会问他 q 个问题，每个问题由两个数字 l 和 r 组成。对于每个问题，Oleg 需要回答满足以下条件的索引集合 (t_1, t_2, ..., t_k) 的数量，其中 k ≥ 1：
1. 对于每个 i 从 1 到 k，满足 l ≤ t_i ≤ r。
2. 对于每个 i 从 1 到 k-1，满足 t_i < t_{i+1}。
3. 对于每个 i 从 1 到 k-1，满足 a_{t_{i+1}} 可以被 a_{t_i} 整除。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——输入数据集的数量。
- 每个数据集的描述如下：
- 第一行包含两个整数 n 和 q（1 ≤ n, q ≤ 10^6）——排列的长度和 Nechipor 的问题数量。
- 第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ n）——排列 a 本身。
- 接下来的 q 行中的每行包含两个整数 l 和 r（1 ≤ l ≤ r ≤ n）——Nechipor 的下一个问题。
- 保证所有测试用例中 n 的值和 q 的值的总和不超过 10^6。

输出：
- 对于每个输入数据集，输出所有 Nechipor 问题的答案。

示例输入：
```
4
8 8
2 1 6 3 5 4 8 7
1 8
2 8
1 7
1 6
1 3
5 8
4 4
2 3
1 1
1
1 1
3 3
3 2 1
1 2
1 3
2 3
8 1
1 2 3 4 5 6 7 8
1 8
```

示例输出：
```
20 15 18 12 5 5 1 3
1
2 3 2
27
```

注意：
- 在第一个输入数据集中，所有合适的数组为：(1), (2), (3), (4), (5), (6), (7), (8), (1, 3), (1, 6), (1, 7), (1, 6, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 6, 7), (6, 7)。
- 在第四个输入数据集中，所有合适的数组为：(1), (2), (3), (4), (5), (6), (7), (8), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 2, 4), (1, 2, 6), (1, 2, 8), (1, 2, 4, 8), (1, 3, 6), (1, 4, 8), (2, 4), (2, 6), (2, 8), (2, 4, 8), (3, 6), (4, 8)。题目大意： Oleg 收到了一个长度为 n 的排列 a 作为生日礼物。他的朋友 Nechipor 会问他 q 个问题，每个问题由两个数字 l 和 r 组成。对于每个问题，Oleg 需要回答满足以下条件的索引集合 (t_1, t_2, ..., t_k) 的数量，其中 k ≥ 1： 1. 对于每个 i 从 1 到 k，满足 l ≤ t_i ≤ r。 2. 对于每个 i 从 1 到 k-1，满足 t_i < t_{i+1}。 3. 对于每个 i 从 1 到 k-1，满足 a_{t_{i+1}} 可以被 a_{t_i} 整除。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4）——输入数据集的数量。 - 每个数据集的描述如下： - 第一行包含两个整数 n 和 q（1 ≤ n, q ≤ 10^6）——排列的长度和 Nechipor 的问题数量。 - 第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ n）——排列 a 本身。 - 接下来的 q 行中的每行包含两个整数 l 和 r（1 ≤ l ≤ r ≤ n）——Nechipor 的下一个问题。 - 保证所有测试用例中 n 的值和 q 的值的总和不超过 10^6。 输出： - 对于每个输入数据集，输出所有 Nechipor 问题的答案。 示例输入： ``` 4 8 8 2 1 6 3 5 4 8 7 1 8 2 8 1 7 1 6 1 3 5 8 4 4 2 3 1 1 1 1 1 3 3 3 2 1 1 2 1 3 2 3 8 1 1 2 3 4 5 6 7 8 1 8 ``` 示例输出： ``` 20 15 18 12 5 5 1 3 1 2 3 2 27 ``` 注意： - 在第一个输入数据集中，所有合适的数组为：(1), (2), (3), (4), (5), (6), (7), (8), (1, 3), (1, 6), (1, 7), (1, 6, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 6, 7), (6, 7)。 - 在第四个输入数据集中，所有合适的数组为：(1), (2), (3), (4), (5), (6), (7), (8), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 2, 4), (1, 2, 6), (1, 2, 8), (1, 2, 4, 8), (1, 3, 6), (1, 4, 8), (2, 4), (2, 6), (2, 8), (2, 4, 8), (3, 6), (4, 8)。