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, \ldots, a_n\) và \(q\) truy vấn (\(1 \leq n, q \leq 5 \cdot 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\).

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, \ldots, 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.

Dữ liệu ra:

• 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 đó.

Input 1

4
2 3 4 5
3
2 1 4 2
1 2 6
2 1 4 2

Output 1

2
1

Giải thích

• Truy vấn đầu tiên: \(\gcd(a_1,2) = 2\), \(\gcd(a_2,2) = 1\), \(\gcd(a_3,2) = 2\), \(\gcd(a_4,2) = 1\) → 2 phần tử có gcd bằng 1 → kết quả là 2.
• Truy vấn cuối: sau khi gán \(a_2 = 6\), chỉ có \(a_4 = 5\) có \(\gcd(a_4,2) = 1\) → kết quả là 1.

Ràng buộc:

• 30% test: \(1 \leq n, q \leq 10^3\);
• 30% test: chỉ gồm các truy vấn loại 2, \(1 \leq n, q \leq 5 \cdot 10^4\);
• 40% test còn lại: như ràng buộc trong đề bài.