Yük stansiyasının əsas yolunda vaqondan ibarət qatar dayanıb. Vaqonlar lokomotivdən başlayaraq -dən -ə qədər nömrələnib və -ci vaqon a_i eyni qutu daşıyır.
Stansiya yükü göndərişlərlə yola salır. Göndəriş — bu, ardıcıl i, i+1, \ldots, j vaqonlarından ibarət qrupdur və onun bütün qutuları konteynerlərə yığılır. Bir göndəriş üçün istifadə olunan bütün konteynerlərin tutumu eyni d \ge 2 olmalıdır və hər vaqon qalıqsız, tam şəkildə yığılmalıdır. Ardıcıl vaqonlardan ibarət qrup, əgər onu bir göndəriş kimi yola salmaq mümkündürsə, yəni elə tam d \ge 2 ədədi varsa ki, qrupun hər vaqonundakı qutuların sayı -yə bölünür, əlverişli adlanır. Başqa sözlə, qrup yalnız və yalnız o halda əlverişlidir ki, \gcd(a_i, a_{i+1}, \ldots, a_j) > 1. a_i \ge 2 qutu daşıyan tək vaqon əlverişli qrup təşkil edir; dəqiq bir qutu daşıyan vaqon isə yox.
Gün ərzində iki növdən olan mesaj daxil olur:
1 p x — vaqonu yenidən yüklənib və indi qutu daşıyır, yəni a_p -ə bərabər olur;
2 l r — dispetçer yalnız l, l+1, \ldots, r vaqonlarından ibarət neçə əlverişli qrupun olduğunu, yəni l \le i \le j \le r şərtini ödəyən və \gcd(a_i, a_{i+1}, \ldots, a_j) > 1 olan cütlərinin sayını bilmək istəyir.
İkinci növdən olan bütün mesajlara cavab verin.
Birinci sətirdə bir tam ədəd (1 \le t \le 3 \cdot 10^5) — test hallarının sayı verilir.
Hər test halının birinci sətrində iki tam ədəd və (1 \le n, q \le 3 \cdot 10^5) — vaqonların sayı və mesajların sayı verilir. İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — qutuların ilkin sayları verilir.
Növbəti sətrin hər biri iki formadan birində mesaj ehtiva edir:
1 p x (1 \le p \le n, 1 \le x \le 10^9);
2 l r (1 \le l \le r \le n).
Bütün test halları üzrə -lərin cəmi 3 \cdot 10^5-i, bütün test halları üzrə -ların cəmi isə 3 \cdot 10^5-i aşmır.
İkinci növdən olan hər mesaj üçün ayrıca sətirdə bir tam ədəd — verilmiş parçanın daxilindəki əlverişli qrupların sayını çap edin. Cavabları mesajların verildiyi ardıcıllıqla, test halı ardınca test halı olmaqla çap edin.
Nümunə 1
Şəkildə birinci test halı göstərilib: iki 2 1 5 mesajı üçün hər əlverişli qrup öz vaqonlarının altında zolaq şəklində təsvir olunub.
Birinci test halında qatar əvvəlcə 2, 6, 3, 1, 4 şəklindədir. -dən -ə qədər vaqonlar qrupu kimi yazılır.
2 1 5 mesajı: əlverişli qruplar , , , , , -dir, deməli cavab -dır. Məsələn, əlverişli deyil, çünki \gcd(2, 6, 3) = 1, və əlverişli deyil, çünki -cü vaqon bir qutu daşıyır.
2 2 3 mesajı: əlverişli qruplar , , -dür, deməli cavab -dür.
1 4 8 mesajı: qatar 2, 6, 3, 8, 4 şəklini alır.
2 1 5 mesajı: əlverişli qruplar , , , , , , , -dir, deməli cavab -dir.
2 3 5 mesajı: əlverişli qruplar , , , -dir, deməli cavab -dür.
İkinci test halında qatar 2, 2, 3, 3 şəklindədir.
2 1 4 mesajı: əlverişli qruplar , , , , , -dür, deməli cavab -dır. və vaqonlarının hər ikisini ehtiva edən heç bir qrup əlverişli deyil, çünki \gcd(2, 3) = 1.
2 2 3 mesajı: əlverişli qruplar və -dür, deməli cavab -dir.
Üçüncü test halında qatar şəklindədir.
2 1 1 mesajı: yeganə vaqon bir qutu daşıyır, buna görə də əlverişli qrup yoxdur və cavab -dır.