Cắt dãy

Cho một dãy số nguyên dương $a_1,a_2,\dots ,a_n$.

Với một đoạn liên tiếp, ta nói đoạn đó hợp lệ nếu tích của tất cả các phần tử trong đoạn bằng bội chung nhỏ nhất (BCNN) của chúng. Điều này tương đương với việc mọi cặp phần tử trong đoạn đều nguyên tố cùng nhau (không chia sẻ ước nguyên tố chung nào).

Cho $q$ truy vấn độc lập. Mỗi truy vấn gồm hai số $l,r$: hãy chia đoạn $a_l,a_{l+1},\dots ,a_r$ thành ít nhất các đoạn con liên tiếp sao cho mỗi đoạn con đều hợp lệ. In ra số đoạn con nhỏ nhất cần thiết.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ mô tả một truy vấn.

Dữ liệu ra

• Với mỗi truy vấn, in ra trên một dòng số đoạn con nhỏ nhất.

Ràng buộc

• $1\le n,q\le {10}^5$
• $1\le a_i\le {10}^5$
• $1\le l\le r\le n$

Ví dụ