Трійки з НСД від Нассера

Вхідні дані

Кожен тест містить декілька тестових випадків. Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків. Далі йде опис тестових випадків.

Перший рядок кожного тестового випадку містить два цілих числа $n$ та $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).

Другий рядок кожного тестового випадку містить $n$ цілих чисел $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) — елементи масиву.

Кожен з наступних $q$ рядків містить два цілих числа $l$ та $r$ $(1 \leq l \leq r \leq n)$ (1 \le l \le r \le n).

Гарантується, що сума $n$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5, а сума $q$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного запиту виведіть одне ціле число — кількість трійок $(i, j, k)$ (i, j, k), для яких $g cd$ належить відрізку $[l, r]$ [l, r], за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1

Loading

Примітка

У першому тестовому випадку $n = 6$ n=6, $q = 2$ q=2, $a = [2, 3, 2, 5, 6, 6]$ a=[2,3,2,5,6,6]:

Запит $1$ : $l = 2$ l=2, $r = 4$ r=4. Потрібні трійки $(i, j, k)$ (i,j,k), для яких $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. Підходить.
$(1, 3, 6)$ (1,3,6): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Підходить.
$(1, 5, 6)$ (1,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Підходить.
$(3, 5, 6)$ (3,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Підходить.
$(5, 6, ?)$ (5,6,?): Потрібен третій елемент. $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. Підходить.

Існує $5$ підходящих трійок. Відповідь — $5$ .

Запит $2$ : $l = 3$ l=3, $r = 4$ r=4. Потрібні трійки $(i, j, k)$ (i,j,k), для яких $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. Підходить.

Існує $1$ підходяща трійка. Відповідь — $1$ .

Оцінювання

Підзадача $1$ ( $30$ балів) : $(3 \leq \sum n \leq 50, 1 \leq \sum q \leq 50)$ (3 \le \sum n \le 50, 1 \le \sum q \le 50)
Підзадача $2$ ( $60$ балів) : $(3 \leq \sum n \leq 500, 1 \leq \sum q \leq 500)$ (3 \le \sum n \le 500, 1 \le \sum q \le 500)
Підзадача $3$ ( $90$ балів) : $(3 \leq \sum n \leq 2000, 1 \leq \sum q \leq 2000)$ (3 \le \sum n \le 2000, 1 \le \sum q \le 2000)
Підзадача $4$ ( $120$ балів) : Без додаткових обмежень.