F. Nobody is needed
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard 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.

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