GCDispower

Problem Description

There is a mysterious organization called GCD. They get a permutation P, permutation is a sequence of length N, only consists of number 1 to N and each number appears only once. They want to gain magic power from this permutation. For the interval [L, R] they can get power: $\sum\limits_{i=L}^R\sum\limits_{j=i+1}^R\sum\limits_{k=j+1}^R (gcd(P[i], P[j]) == P[k]) \cdot P[k]$ Now they have M queries, for each query can you help them calculate how many power they can get£¿

Input

The first line is an integer T which indicates the case number. And as for each case, first line is two integer N and M which indicates the length of permutation and number of query. Next line is N integer which indicate the permutation P Next M line, for each line is two integer L and R which indicate each query. Limit $1 \leq T \leq 100$ $1 \leq N, M \leq100000$ $1 \leq Pi \leq N$, for any pair $(i, j)$, $Pi \neq Pj$ $1 \leq Li \leq Ri \leq N$ About 95% test case: $1 \leq N \leq 1000$ Other test case: $1 \leq N \leq 100000$

Output

As for each case, you need to output M integer which indicate the answer of each query.

Sample Input

2

3 1

3 2 1

1 3

6 3

6 5 4 3 2 1

1 6

2 6

3 5

Sample Output

1

8

5

0

Source

2017 Multi-University Training Contest - Team 6

https://acm.hdu.edu.cn/showproblem.php?pid=6102