Зручні партії#13104

Зручні партії

9 секунд
256 мегабайтів

На головній колії вантажної станції стоїть потяг з вагонів. Вагони пронумеровано від до , починаючи від локомотива, і -й вагон везе a_i однакових ящиків.

Станція відправляє вантаж партіями. Партія — це група послідовних вагонів i, i+1, \ldots, j, усі ящики якої пакують у контейнери. Усі контейнери для однієї партії мусять мати однакову місткість d \ge 2, і кожен вагон треба запакувати повністю, без залишку. Групу послідовних вагонів називають зручною, якщо її можна відправити однією партією, тобто якщо існує ціле число d \ge 2 таке, що кількість ящиків у кожному вагоні групи ділиться на . Інакше кажучи, група зручна тоді й лише тоді, коли \gcd(a_i, a_{i+1}, \ldots, a_j) > 1. Один вагон з a_i \ge 2 ящиками утворює зручну групу; вагон рівно з одним ящиком — ні.

Протягом дня надходять повідомлень двох видів:

Дайте відповіді на всі повідомлення другого виду.

Вхідні дані

Перший рядок містить ціле число (1 \le t \le 3 \cdot 10^5) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить два цілі числа і (1 \le n, q \le 3 \cdot 10^5) — кількість вагонів і кількість повідомлень. Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — початкові кількості ящиків.

Кожен з наступних рядків містить повідомлення в одному з двох видів:

  • 1 p x (1 \le p \le n, 1 \le x \le 10^9);

  • 2 l r (1 \le l \le r \le n).

Сума за всіма тестовими випадками не перевищує 3 \cdot 10^5, і сума за всіма тестовими випадками не перевищує 3 \cdot 10^5.

Вихідні дані

Для кожного повідомлення другого виду виведіть одне ціле число в окремому рядку — кількість зручних груп усередині заданого відрізка. Виводьте відповіді в тому порядку, в якому задано повідомлення, тестовий випадок за тестовим випадком.

Приклади

Приклад 1

Loading
Loading

Примітка

На рисунку показано перший тестовий випадок: кожну зручну групу для двох повідомлень 2 1 5 зображено смужкою під її вагонами.

У першому тестовому випадку потяг спочатку має вигляд 2, 6, 3, 1, 4. Групу вагонів від до позначимо .

  • Повідомлення 2 1 5: зручні групи — , , , , , , тож відповідь — . Наприклад, не зручна, бо \gcd(2, 6, 3) = 1, а не зручна, бо вагон везе один ящик.

  • Повідомлення 2 2 3: зручні групи — , , , тож відповідь — .

  • Повідомлення 1 4 8: потяг набуває вигляду 2, 6, 3, 8, 4.

  • Повідомлення 2 1 5: зручні групи — , , , , , , , , тож відповідь — .

  • Повідомлення 2 3 5: зручні групи — , , , , тож відповідь — .

У другому тестовому випадку потяг має вигляд 2, 2, 3, 3.

  • Повідомлення 2 1 4: зручні групи — , , , , , , тож відповідь — . Жодна група, що містить обидва вагони і , не зручна, оскільки \gcd(2, 3) = 1.

  • Повідомлення 2 2 3: зручні групи — і , тож відповідь — .

У третьому тестовому випадку потяг має вигляд .

  • Повідомлення 2 1 1: єдиний вагон везе один ящик, тому зручних груп немає і відповідь — .