Nasser'in EBOB Üçlüleri

Giriş

Her test birden fazla test durumu içerir. İlk satırda tek bir tam sayı $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — test durumlarının sayısı verilir. Ardından test durumlarının açıklaması gelir.

Her test durumunun ilk satırında iki tam sayı $n$ ve $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) verilir.

Her test durumunun ikinci satırında $n$ tam sayı $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) — dizinin elemanları verilir.

Sonraki $q$ satırın her birinde iki tam sayı $l$ ve $r$ $(1 \leq l \leq r \leq n)$ (1 \le l \le r \le n) verilir.

Tüm test durumları üzerinden $n$ değerlerinin toplamının $2 \cdot 1 0^{5}$ 2 \cdot 10^5'i ve $q$ değerlerinin toplamının $2 \cdot 1 0^{5}$ 2 \cdot 10^5'i aşmadığı garanti edilir.

Çıktı

Her sorgu için tek bir tam sayı — $g cd$ değeri $[l, r]$ [l, r] aralığında olan $(i, j, k)$ (i, j, k) üçlülerinin sayısını $1 0^{9} + 7$ 10^9 + 7 moduna göre yazdırın.

Örnekler

Örnek 1

Loading

Not

Birinci test durumunda $n = 6$ n=6, $q = 2$ q=2, $a = [2, 3, 2, 5, 6, 6]$ a=[2,3,2,5,6,6]:

Sorgu $1$ : $l = 2$ l=2, $r = 4$ r=4. $2 \leq g cd (a_{i}, a_{j}, a_{k}) \leq 4$ 2 \le \gcd(a_i, a_j, a_k) \le 4 koşulunu sağlayan $(i, j, k)$ (i,j,k) üçlülerine ihtiyacımız var.

$(1, 3, 5)$ (1,3,5): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Geçerli.
$(1, 3, 6)$ (1,3,6): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Geçerli.
$(1, 5, 6)$ (1,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Geçerli.
$(3, 5, 6)$ (3,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Geçerli.
$(5, 6, ?)$ (5,6,?): Üçüncü bir elemana ihtiyacımız var. $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. Geçerli.

$5$ geçerli üçlü vardır. Cevap $5$ 'tir.

Sorgu $2$ : $l = 3$ l=3, $r = 4$ r=4. $3 \leq g cd (a_{i}, a_{j}, a_{k}) \leq 4$ 3 \le \gcd(a_i, a_j, a_k) \le 4 koşulunu sağlayan $(i, j, k)$ (i,j,k) üçlülerine ihtiyacımız var.

$(2, 5, 6)$ (2,5,6): $g cd (3, 6, 6) = 3$ \gcd(3,6,6)=3. Geçerli.

$1$ geçerli üçlü vardır. Cevap $1$ 'dir.

Puanlama

Alt görev $1$ ( $30$ puan) : $(3 \leq \sum n \leq 50, 1 \leq \sum q \leq 50)$ (3 \le \sum n \le 50, 1 \le \sum q \le 50)
Alt görev $2$ ( $60$ puan) : $(3 \leq \sum n \leq 500, 1 \leq \sum q \leq 500)$ (3 \le \sum n \le 500, 1 \le \sum q \le 500)
Alt görev $3$ ( $90$ puan) : $(3 \leq \sum n \leq 2000, 1 \leq \sum q \leq 2000)$ (3 \le \sum n \le 2000, 1 \le \sum q \le 2000)
Alt görev $4$ ( $120$ puan) : Ek kısıt yoktur.