На головній колії вантажної станції стоїть потяг з вагонів. Вагони пронумеровано від до , починаючи від локомотива, і -й вагон везе 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 p x — вагон перевантажили, і тепер він везе ящиків, тобто a_p стає рівним ;
2 l r — диспетчер хоче дізнатися, скільки зручних груп складаються лише з вагонів l, l+1, \ldots, r, тобто кількість пар з l \le i \le j \le r таких, що \gcd(a_i, a_{i+1}, \ldots, a_j) > 1.
Дайте відповіді на всі повідомлення другого виду.
Перший рядок містить ціле число (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
На рисунку показано перший тестовий випадок: кожну зручну групу для двох повідомлень 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: єдиний вагон везе один ящик, тому зручних груп немає і відповідь — .