En la vía principal de una estación de carga se encuentra un tren de vagones. Los vagones están numerados de a a partir de la locomotora, y el -ésimo vagón transporta a_i cajas idénticas.
La estación despacha la carga en envíos. Un envío es un grupo de vagones consecutivos i, i+1, \ldots, j, y todas sus cajas se empaquetan en contenedores. Todos los contenedores utilizados para un mismo envío deben tener la misma capacidad d \ge 2, y cada vagón debe empaquetarse por completo, sin sobrantes. Un grupo de vagones consecutivos se llama conveniente si puede despacharse como un solo envío, es decir, si existe un entero d \ge 2 tal que la cantidad de cajas de cada vagón del grupo es divisible por . En otras palabras, el grupo es conveniente si y solo si \gcd(a_i, a_{i+1}, \ldots, a_j) > 1. Un único vagón con a_i \ge 2 cajas forma un grupo conveniente; un vagón con exactamente una caja, no.
Durante el día llegan mensajes de dos tipos:
1 p x — el vagón ha sido recargado y ahora transporta cajas, es decir, a_p pasa a ser igual a ;
2 l r — el despachador quiere saber cuántos grupos convenientes están formados únicamente por los vagones l, l+1, \ldots, r, es decir, la cantidad de pares con l \le i \le j \le r tales que \gcd(a_i, a_{i+1}, \ldots, a_j) > 1.
Responda todos los mensajes del segundo tipo.
La primera línea contiene un entero (1 \le t \le 3 \cdot 10^5) — la cantidad de casos de prueba.
La primera línea de cada caso de prueba contiene dos enteros y (1 \le n, q \le 3 \cdot 10^5) — la cantidad de vagones y la cantidad de mensajes. La segunda línea contiene enteros a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — las cantidades iniciales de cajas.
Cada una de las siguientes líneas contiene un mensaje en una de las dos formas:
1 p x (1 \le p \le n, 1 \le x \le 10^9);
2 l r (1 \le l \le r \le n).
La suma de sobre todos los casos de prueba no supera 3 \cdot 10^5, y la suma de sobre todos los casos de prueba no supera 3 \cdot 10^5.
Para cada mensaje del segundo tipo imprima un entero en una línea aparte — la cantidad de grupos convenientes dentro del segmento dado. Imprima las respuestas en el orden en que se dan los mensajes, caso de prueba tras caso de prueba.
Ejemplo 1
La figura muestra el primer caso de prueba: cada grupo conveniente correspondiente a los dos mensajes 2 1 5 está dibujado como una barra debajo de sus vagones.
En el primer caso de prueba el tren es inicialmente 2, 6, 3, 1, 4. Un grupo de vagones desde hasta se escribe como .
Mensaje 2 1 5: los grupos convenientes son , , , , , , así que la respuesta es . Por ejemplo, no es conveniente porque \gcd(2, 6, 3) = 1, y no es conveniente porque el vagón transporta una caja.
Mensaje 2 2 3: los grupos convenientes son , , , así que la respuesta es .
Mensaje 1 4 8: el tren pasa a ser 2, 6, 3, 8, 4.
Mensaje 2 1 5: los grupos convenientes son , , , , , , , , así que la respuesta es .
Mensaje 2 3 5: los grupos convenientes son , , , , así que la respuesta es .
En el segundo caso de prueba el tren es 2, 2, 3, 3.
Mensaje 2 1 4: los grupos convenientes son , , , , , , así que la respuesta es . Ningún grupo que contenga a la vez los vagones y es conveniente, puesto que \gcd(2, 3) = 1.
Mensaje 2 2 3: los grupos convenientes son y , así que la respuesta es .
En el tercer caso de prueba el tren es .
Mensaje 2 1 1: el único vagón transporta una caja, por lo que no hay grupos convenientes y la respuesta es .