Nasser's GCD Triples

Input

Each test contains multiple test cases. The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5).

The second line of each test case contains $n$ integers a_1, a_2, \ldots, a_n (1 \le a_i \le n) — the elements of the array.

The next $q$ lines each contain two integers $l$ and $r$ (1 \le l \le r \le n).

It is guaranteed that the sum of $n$ over all test cases does not exceed 2 \cdot 10^5, and the sum of $q$ over all test cases does not exceed 2 \cdot 10^5.

Output

For each query, print a single integer — the number of triples (i, j, k) with $\gcd$ in [l, r], modulo 10^9 + 7.

Examples

Note

In the first test case, n=6, q=2, a=[2,3,2,5,6,6]:

Query $1$: l=2, r=4. We need triples (i,j,k) where 2 \le \gcd(a_i, a_j, a_k) \le 4.

• (1,3,5): \gcd(2,2,6)=2. Valid.

• (1,3,6): \gcd(2,2,6)=2. Valid.

• (1,5,6): \gcd(2,6,6)=2. Valid.

• (3,5,6): \gcd(2,6,6)=2. Valid.

• (5,6,?): We need a third element. \gcd(6,6,2)=2, \gcd(6,6,3)=3.

• (2,5,6): \gcd(3,6,6)=3. Valid.

There are $5$ valid triples. The answer is $5$.

Query $2$: l=3, r=4. We need triples (i,j,k) where 3 \le \gcd(a_i, a_j, a_k) \le 4.

• (2,5,6): \gcd(3,6,6)=3. Valid.

There is $1$ valid triple. The answer is $1$.

Scoring

1. Subtask $1$ ($30$ points) : (3 \le \sum n \le 50, 1 \le \sum q \le 50)

2. Subtask $2$ ($60$ points) : (3 \le \sum n \le 500, 1 \le \sum q \le 500)

3. Subtask $3$ ($90$ points) : (3 \le \sum n \le 2000, 1 \le \sum q \le 2000)

4. Subtask $4$ ($120$ points) : No additional constraints.