Nasserin ƏBOB üçlükləri

Giriş

Hər test bir neçə test blokundan ibarətdir. Birinci sətirdə bir tam ədəd $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — test bloklarının sayı verilir. Sonra test bloklarının təsviri gəlir.

Hər test blokunun birinci sətrində iki tam ədəd $n$ və $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.

Hər test blokunun ikinci sətrində $n$ tam ədəd $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) — massivin elementləri verilir.

Növbəti $q$ sətrin hər birində iki tam ədəd $l$ və $r$ $(1 \leq l \leq r \leq n)$ (1 \le l \le r \le n) verilir.

Bütün test blokları üzrə $n$ -lərin cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i, $q$ -ların cəminin isə $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i aşmadığı təmin edilir.

Çıxış

Hər sorğu üçün bir tam ədəd — $g cd$ qiyməti $[l, r]$ [l, r] aralığında olan $(i, j, k)$ (i, j, k) üçlüklərinin sayını $1 0^{9} + 7$ 10^9 + 7 moduluna görə çıxarın.

Nümunələr

Nümunə 1

Loading

Qeyd

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

$1$ -ci sorğu: $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 şərtini ödəyən $(i, j, k)$ (i,j,k) üçlükləri lazımdır.

$(1, 3, 5)$ (1,3,5): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Uyğundur.
$(1, 3, 6)$ (1,3,6): $g cd (2, 2, 6) = 2$ \gcd(2,2,6)=2. Uyğundur.
$(1, 5, 6)$ (1,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Uyğundur.
$(3, 5, 6)$ (3,5,6): $g cd (2, 6, 6) = 2$ \gcd(2,6,6)=2. Uyğundur.
$(5, 6, ?)$ (5,6,?): Üçüncü element lazımdır. $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. Uyğundur.

Uyğun gələn $5$ üçlük var. Cavab $5$ -dir.

$2$ -ci sorğu: $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 şərtini ödəyən $(i, j, k)$ (i,j,k) üçlükləri lazımdır.

$(2, 5, 6)$ (2,5,6): $g cd (3, 6, 6) = 3$ \gcd(3,6,6)=3. Uyğundur.

Uyğun gələn $1$ üçlük var. Cavab $1$ -dir.

Bal hesablama

$1$ -ci altməsələ ( $30$ bal) : $(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$ -ci altməsələ ( $60$ bal) : $(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$ -cü altməsələ ( $90$ bal) : $(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$ -cü altməsələ ( $120$ bal) : Əlavə məhdudiyyət yoxdur.