Tripletas con MCD de Nasser

Entrada

Cada test contiene múltiples casos de prueba. La primera línea contiene un único entero $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — la cantidad de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n$ y $q$ $(3 \leq n \leq 2 \cdot 1 0^{5}, 1 \leq q \leq 2 \cdot 1 0^{5})$ (3 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5).

La segunda línea de cada caso de prueba contiene $n$ enteros $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{i} \leq n)$ (1 \le a_i \le n) — los elementos del arreglo.

Cada una de las siguientes $q$ líneas contiene dos enteros $l$ y $r$ $(1 \leq l \leq r \leq n)$ (1 \le l \le r \le n).

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $2 \cdot 1 0^{5}$ 2 \cdot 10^5, y que la suma de $q$ sobre todos los casos de prueba no excede $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Salida

Para cada consulta, imprime un único entero — la cantidad de tripletas $(i, j, k)$ (i, j, k) cuyo $g cd$ está en $[l, r]$ [l, r], módulo $1 0^{9} + 7$ 10^9 + 7.

Ejemplos

Ejemplo 1

Loading

Nota

En el primer caso de prueba, $n = 6$ n=6, $q = 2$ q=2, $a = [2, 3, 2, 5, 6, 6]$ a=[2,3,2,5,6,6]:

Consulta $1$ : $l = 2$ l=2, $r = 4$ r=4. Necesitamos tripletas $(i, j, k)$ (i,j,k) donde $2 \leq g cd (a_{i}, a_{j}, a_{k}) \leq 4$ 2 \le \gcd(a_i, a_j, a_k) \le 4.

$(1, 3, 5)$ (1,3,5): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Válida.
$(1, 3, 6)$ (1,3,6): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Válida.
$(1, 5, 6)$ (1,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Válida.
$(3, 5, 6)$ (3,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Válida.
$(5, 6, ?)$ (5,6,?): Necesitamos un tercer elemento. $g cd (6, 6, 2) = 2$ \gcd(6,6,2)=2, $g cd (6, 6, 3) = 3$ \gcd(6,6,3)=3.
$(2, 5, 6)$ (2,5,6): $g cd (3, 6, 6) = 3$ \gcd(3,6,6)=3. Válida.

Hay $5$ tripletas válidas. La respuesta es $5$ .

Consulta $2$ : $l = 3$ l=3, $r = 4$ r=4. Necesitamos tripletas $(i, j, k)$ (i,j,k) donde $3 \leq g cd (a_{i}, a_{j}, a_{k}) \leq 4$ 3 \le \gcd(a_i, a_j, a_k) \le 4.

$(2, 5, 6)$ (2,5,6): $g cd (3, 6, 6) = 3$ \gcd(3,6,6)=3. Válida.

Hay $1$ tripleta válida. La respuesta es $1$ .

Puntuación

Subtarea $1$ ( $30$ puntos) : $(3 \leq \sum n \leq 50, 1 \leq \sum q \leq 50)$ (3 \le \sum n \le 50, 1 \le \sum q \le 50)
Subtarea $2$ ( $60$ puntos) : $(3 \leq \sum n \leq 500, 1 \leq \sum q \leq 500)$ (3 \le \sum n \le 500, 1 \le \sum q \le 500)
Subtarea $3$ ( $90$ puntos) : $(3 \leq \sum n \leq 2000, 1 \leq \sum q \leq 2000)$ (3 \le \sum n \le 2000, 1 \le \sum q \le 2000)
Subtarea $4$ ( $120$ puntos) : Sin restricciones adicionales.