Зведення простими числами

Вхідні дані

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

Перший рядок кожного тестового випадку містить два цілих числа $n$ та $q$ ( $1 \leq n, q \leq 5 \cdot 1 0^{5}$ 1 \le n, q \le 5 \cdot 10^5) — розмір масиву та кількість оновлень.

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

Далі йдуть $q$ рядків. Кожен рядок містить два цілих числа $i d x$ та $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), які описують оновлення.

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

Вихідні дані

Для кожного тестового випадку виведіть $q$ рядків. $j$ -й рядок має містити одне ціле число — мінімальну кількість операцій, необхідних Фаді, щоб зробити всі елементи масиву рівними $1$ після $j$ -го оновлення.

Приклади

Приклад 1

Loading

Примітка

У першому тестовому випадку початковий масив $a = [12, 6, 12, 2]$ a = [12, 6, 12, 2].

Після першого оновлення масив стає $a = [12, 1, 12, 2]$ a = [12, 1, 12, 2]. Мінімальна кількість операцій дорівнює $6$ :

Застосувати $3$ операції до $a_{1}$ a_1 ( $p \in {2, 2, 3}$ p \in \{2, 2, 3\}).
Застосувати $3$ операції до підвідрізка $[3, 4]$ . Операція з $p = 2$ p=2 застосовується одночасно до $a_{3}$ a_3 та $a_{4}$ a_4, тоді як операції з $p \in {2, 3}$ p \in \{2, 3\} застосовуються лише до $a_{3}$ a_3.

Після другого оновлення масив стає $a = [12, 1, 2, 2]$ a = [12, 1, 2, 2]. Мінімальна кількість операцій дорівнює $4$ :

Застосувати $3$ операції до $a_{1}$ a_1 ( $p \in {2, 2, 3}$ p \in \{2, 2, 3\}).
Застосувати $1$ операцію до підвідрізка $[3, 4]$ ( $p = 2$ p=2).

У другому тестовому випадку масив спочатку дорівнює $a = [30, 30, 30]$ a = [30, 30, 30]. Після першого оновлення він стає $a = [30, 1, 30]$ a = [30, 1, 30]. Оскільки $a_{2} = 1$ a_2 = 1, решта елементів не можуть мати спільних операцій. Ми застосовуємо $3$ операції ( $p \in {2, 3, 5}$ p \in \{2, 3, 5\}) до $a_{1}$ a_1 та $3$ операції до $a_{3}$ a_3, разом $6$ операцій.

Оцінювання

Підзадача $1$ ( $100$ балів): $\sum n \leq 2000$ \sum n \le 2000 та $\sum q \leq 2000$ \sum q \le 2000.
Підзадача $2$ ( $100$ балів): $1 \leq a_{i}, x \leq 1000$ 1 \le a_i, x \le 1000.
Підзадача $3$ ( $200$ балів): Без додаткових обмежень.