codeforces#P1946F. Nobody is needed

    ID: 34518 远端评测题 6000ms 512MiB 尝试: 0 已通过: 0 难度: 9 上传者: 标签>brute forcedata structuresdpmathnumber theory*2500

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$).