Bir yük istasyonunun ana hattında vagondan oluşan bir tren durmaktadır. Vagonlar lokomotiften başlayarak 'den 'ye kadar numaralandırılmıştır ve -inci vagon a_i adet özdeş kutu taşımaktadır.
İstasyon yükü sevkiyatlar hâlinde gönderir. Bir sevkiyat, ardışık i, i+1, \ldots, j vagonlarından oluşan bir gruptur ve bu grubun bütün kutuları konteynerlere paketlenir. Bir sevkiyat için kullanılan tüm konteynerlerin kapasitesi aynı d \ge 2 olmalıdır ve her vagon artık kalmadan tamamen paketlenmelidir. Ardışık vagonlardan oluşan bir grup, tek bir sevkiyat olarak gönderilebiliyorsa, yani grubun her vagonundaki kutu sayısı 'ye bölünecek şekilde bir d \ge 2 tam sayısı varsa, uygun olarak adlandırılır. Başka bir deyişle, grup ancak ve ancak \gcd(a_i, a_{i+1}, \ldots, a_j) > 1 ise uygundur. a_i \ge 2 kutu taşıyan tek bir vagon uygun bir grup oluşturur; tam olarak bir kutu taşıyan bir vagon ise oluşturmaz.
Gün boyunca iki türde toplam mesaj gelir:
1 p x — vagonu yeniden yüklenmiştir ve artık kutu taşımaktadır, yani a_p değeri 'e eşit olur;
2 l r — sevk memuru yalnızca l, l+1, \ldots, r vagonlarından oluşan kaç uygun grup bulunduğunu, yani l \le i \le j \le r olmak üzere \gcd(a_i, a_{i+1}, \ldots, a_j) > 1 koşulunu sağlayan çiftlerinin sayısını öğrenmek ister.
İkinci türden tüm mesajları yanıtlayın.
İlk satırda bir tam sayı (1 \le t \le 3 \cdot 10^5) — test durumlarının sayısı verilir.
Her test durumunun ilk satırında iki tam sayı ve (1 \le n, q \le 3 \cdot 10^5) — vagonların sayısı ve mesajların sayısı verilir. İkinci satırda tam sayı a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — kutuların başlangıçtaki sayıları verilir.
Sonraki satırın her biri iki biçimden birinde bir mesaj içerir:
1 p x (1 \le p \le n, 1 \le x \le 10^9);
2 l r (1 \le l \le r \le n).
Tüm test durumları üzerinden değerlerinin toplamı 3 \cdot 10^5'i, tüm test durumları üzerinden değerlerinin toplamı ise 3 \cdot 10^5'i aşmaz.
İkinci türden her mesaj için ayrı bir satırda bir tam sayı — verilen aralığın içindeki uygun grupların sayısını yazdırın. Yanıtları mesajların verildiği sırayla, test durumu test durumu ardından olacak şekilde yazdırın.
Örnek 1
Şekilde birinci test durumu gösterilmektedir: iki 2 1 5 mesajı için her uygun grup, kendi vagonlarının altında bir çubuk olarak çizilmiştir.
Birinci test durumunda tren başlangıçta 2, 6, 3, 1, 4 şeklindedir. 'den 'ye kadar olan vagon grubu olarak yazılır.
2 1 5 mesajı: uygun gruplar , , , , , olduğundan yanıt 'dır. Örneğin, uygun değildir çünkü \gcd(2, 6, 3) = 1, ve uygun değildir çünkü numaralı vagon bir kutu taşımaktadır.
2 2 3 mesajı: uygun gruplar , , olduğundan yanıt 'tür.
1 4 8 mesajı: tren 2, 6, 3, 8, 4 hâline gelir.
2 1 5 mesajı: uygun gruplar , , , , , , , olduğundan yanıt 'dir.
2 3 5 mesajı: uygun gruplar , , , olduğundan yanıt 'tür.
İkinci test durumunda tren 2, 2, 3, 3 şeklindedir.
2 1 4 mesajı: uygun gruplar , , , , , olduğundan yanıt 'dır. ve numaralı vagonların ikisini birden içeren hiçbir grup uygun değildir, çünkü \gcd(2, 3) = 1.
2 2 3 mesajı: uygun gruplar ve olduğundan yanıt 'dir.
Üçüncü test durumunda tren şeklindedir.
2 1 1 mesajı: tek vagon bir kutu taşımaktadır, bu yüzden uygun grup yoktur ve yanıt 'dır.