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.

见题面 Input 部分

见题面 Output 部分

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