Thắng thích làm những bài toán liên quan đến truy vấn với các con số. Một hôm Thắng tìm được một bài toán mới mà anh ta cho rằng khá khó để giải quyết. Do đó, anh ta nhờ bạn giúp!

Cho một dãy số nguyên \(a_{1},\ a_{2},\ ...,\ a_{n}\) và \(q\) truy vấn \((1 \leq n,\ q \leq \ {5.10}^{4};\ 1 \leq a_{i} \leq 10^{5})\). Có 2 loại truy vấn sau:

+ \(1\ x\ y\): Gán \(a_{x}\ = \ y\) (\(1 \leq x \leq n,\ 1 \leq y \leq 10^{5},\ x,\ y\) là số nguyên);

+ \(2\ l\ r\ g\): Đếm các chỉ số i sao cho \(l \leq i \leq r\) và \(gcd(a_{i},\ g) = 1\) \((1 \leq l \leq r \leq n,\ 1 \leq g \leq \ 10^{5},\ l,\ r,\ g\) là các số nguyên). Kí hiệu \(gcd(a_{i},\ g)\) là ước chung lớn nhất của \(a_{i}\) và \(g\).

Hãy đưa ra câu trả lời cho mỗi truy vấn loại 2.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(n\) là số phần tử của dãy.

+ Dòng thứ hai chứa \(n\) số nguyên \(a_{1},\ a_{2},\ ...,\ a_{n}\).

+ Dòng thứ ba chứa số nguyên \(q\) là số truy vấn.

+ Mỗi dòng trong \(q\) dòng tiếp theo chứa một truy vấn thuộc 2 dạng như mô tả ở trên.

Kết quả:

+ Với mỗi truy vấn loại 2, ghi ra trên một dòng chứa một số nguyên là câu trả lời của truy vấn đó.

Ví dụ:

Với truy vấn đầu tiên: \(gcd(a_{1},\ 2) = 2\), \(gcd(a_{2},\ 2) = 1\), \(gcd(a_{3},\ 2) = 2\) và \(gcd(a_{4},\ 2) = 1\), do đó câu trả lời là 2.

Với truy vấn thứ ba: chỉ có gcd(a₄, 2) = 1, do đó câu trả lời là 1.

Ràng buộc:

• Có 30% test: \(1 \leq n,\ q \leq 10^{3}\);

• Có 30% test: Chỉ gồm các truy vấn loại 2, \(1 \leq n,\ q \leq 5.10^{4}\);

• Có 40% test còn lại: Như ràng buộc trong đề bài.