Asal Sayılarla İndirgeme

Giriş

İlk satırda bir tam sayı $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test durumlarının sayısı verilir.

Her test durumunun ilk satırında iki tam sayı $n$ ve $q$ ( $1 \leq n, q \leq 5 \cdot 1 0^{5}$ 1 \le n, q \le 5 \cdot 10^5) — dizinin boyutu ve güncelleme sayısı verilir.

İkinci satırda $n$ tam sayı $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $1 \leq a_{i} \leq 1 0^{7}$ 1 \le a_i \le 10^7) — dizinin başlangıçtaki elemanları verilir.

Ardından $q$ satır gelir. Her satırda bir güncellemeyi tanımlayan iki tam sayı $i d x$ ve $x$ ( $1 \leq i d x \leq n$ 1 \le idx \le n, $1 \leq x \leq 1 0^{7}$ 1 \le x \le 10^7) bulunur.

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

Çıktı

Her test durumu için $q$ satır yazdırın. $j$ -inci satırda tek bir tam sayı — $j$ -inci güncellemeden sonra dizinin bütün elemanlarını $1$ 'e eşit yapmak için Fady'nin ihtiyaç duyduğu en az işlem sayısı bulunmalıdır.

Örnekler

Örnek 1

Loading

Not

Birinci test durumunda başlangıç dizisi $a = [12, 6, 12, 2]$ a = [12, 6, 12, 2]'dir.

Birinci güncellemeden sonra dizi $a = [12, 1, 12, 2]$ a = [12, 1, 12, 2] olur. En az işlem sayısı $6$ 'dır:

$a_{1}$ a_1'e $3$ işlem uygulanır ( $p \in {2, 2, 3}$ p \in \{2, 2, 3\}).
$[3, 4]$ alt parçasına $3$ işlem uygulanır. $p = 2$ p=2 işlemi aynı anda hem $a_{3}$ a_3'e hem de $a_{4}$ a_4'e uygulanırken, $p \in {2, 3}$ p \in \{2, 3\} işlemleri yalnızca $a_{3}$ a_3'e uygulanır.

İkinci güncellemeden sonra dizi $a = [12, 1, 2, 2]$ a = [12, 1, 2, 2] olur. En az işlem sayısı $4$ 'tür:

$a_{1}$ a_1'e $3$ işlem uygulanır ( $p \in {2, 2, 3}$ p \in \{2, 2, 3\}).
$[3, 4]$ alt parçasına $1$ işlem uygulanır ( $p = 2$ p=2).

İkinci test durumunda dizi başlangıçta $a = [30, 30, 30]$ a = [30, 30, 30]'dur. Birinci güncellemeden sonra dizi $a = [30, 1, 30]$ a = [30, 1, 30] olur. $a_{2} = 1$ a_2 = 1 olduğundan geriye kalan elemanlar işlemleri paylaşamaz. $a_{1}$ a_1'e $3$ işlem ( $p \in {2, 3, 5}$ p \in \{2, 3, 5\}) ve $a_{3}$ a_3'e $3$ işlem uygularız, toplamda $6$ işlem.

Puanlama

Alt görev $1$ ( $100$ puan): $\sum n \leq 2000$ \sum n \le 2000 ve $\sum q \leq 2000$ \sum q \le 2000.
Alt görev $2$ ( $100$ puan): $1 \leq a_{i}, x \leq 1000$ 1 \le a_i, x \le 1000.
Alt görev $3$ ( $200$ puan): Ek kısıt yoktur.