Nobody is needed
Description
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.
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$.
For each set of input data, output the answers to 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.
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
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$).