Problem Description

$Touma Kazusa$ is dating with $Kitahara Haruki$. To test if $Haruki$ is a skilled man, $Kazusa$ created a function which called $Kazusa$ $function $. Its expression is as follows:

$S(l,r) = \sum_{i=l}^{r}\sum_{j=l}^{r}\varphi(gcd(a_i,a_j))lcm(a_i,a_j)$ .$l$ and $r$ are the left and right endpoints of an interval of sequence $a$, respectively.

However, because this function is really easy for $Haruki$ and $Haruki$ told $Kazusa$ the answer quickly. So $Kazusa$ strengthened the problem.

Now, $Kazusa$ will gives $Haruki$ a sequence $a$ and $q$ intervals, and for each interval, $Haruki$ should calculate $S(l,r)$.$Haruki$ still thinks it's easy for him, but he just want to date with $Kazusa$, So this problem should solved by you.

Because the value of $S(l,r)$ maybe too large, you only need output $S(l,r)$ $mod$ $2^{32}$

Input

There are multiple test cases. The first line of the input contain an integer $T(1 \leq T \leq 100)$, indicating the number of test cases. For each test case:

First line contains two positive integers $n(1 \leq n \leq 1e5)$ and $q(1 \leq q \leq 1e5)$ which are separated by spaces, denoting the length of sequence $a$ and the number of interval.

Second line contains $n$ positive integers $a_1$,$a_2$,$a_3$,...,$a_n$$(1\leq a_i\leq 1e7)$.

Following $q$ lines, each line contain two integers $l, r$.$(1 \leq l \leq r \leq n)$

It is guaranteed that $\sum_{n} \leq 3e5$ and $\sum_{q} \leq 3e5$, and at most two cases $n = 1e5$. When $n = 1e5$,it is guaranteed that all $a_i$ are generated randomly.

Output

Output $q$ lines, each line is an integer, representing the value of $S(l,r)$ $mod$ $2^{32}$.

1
5 1
1 2 3 4 5
1 5

199