write a go solution for 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>=1 such that:

- l<=t_i<=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 Format:
Each test consists of several sets of input data. The first line contains a single integer t (1<=t<=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<=n,q<=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<=a_i<=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<=l<=r<=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 Format:
For each set of input data, output the answers to all of Nechipor's questions.

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).. Output only the code with no comments, explanation, or additional text.