Một số giới hạn của đề bài đã được sửa so với file PDF.

Một nhà khoa học đang quan sát các hành tinh trong vũ trụ, mỗi hành tinh được biểu diễn bằng một số nguyên dương ~a_1, a_2, \dots, a_n~. Các hành tinh được xếp thành một vòng tròn, nghĩa là hành tinh thứ ~n~ nằm cạnh hành tinh thứ ~1~. Hai hành tinh được gọi là cùng quỹ đạo nếu ước số chung lớn nhất (GCD) của chúng khác ~1~. Nhà khoa học muốn chia vòng tròn hành tinh này thành ít nhất các nhóm liên tiếp sao cho trong mỗi nhóm, không có hai hành tinh nào cùng quỹ đạo với nhau.

Ngoài ra, nhà khoa học thực hiện ~q~ lần quan sát. Mỗi lần quan sát, ông chọn một đoạn từ hành tinh thứ ~l~ đến hành tinh thứ ~r~ trên vòng tròn. Nếu ~r \ge l~, đoạn này bao gồm các hành tinh ~a_l, a_{l+1}, \dots, a_r~. Nếu ~r < l~, đoạn này bao gồm các hành tinh từ ~a_r, a_{r+1}, \dots, a_n~ và tiếp tục từ ~a_1, a_2, \dots, a_l~. Nhà khoa học cần xác định với mỗi đoạn thì số lượng nhóm liên tiếp ít nhất có thể chia trong đoạn đó là bao nhiêu?

Hãy giúp nhà khoa học tìm cách chia tối ưu nhất để phân loại các hành tinh theo quỹ đạo của chúng trên vòng tròn!

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ - số hành tinh và số lần quan sát.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 2 \times 10^5)~ - giá trị biểu diễn các hành tinh.

• Trên ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ ~(1 \le l, r \le n)~ - chỉ số hành tinh bắt đầu và kết thúc của đoạn cần xét trên vòng tròn.

Output

• Với mỗi lần quan sát, in ra một số nguyên duy nhất - số lượng nhóm hành tinh liên tiếp ít nhất có thể chia trên đoạn được chọn.

Scoring

Sample Input 1

8 7
2 3 10 7 6 14 5 7
1 8
1 6
2 7
7 3
4 1
3 6
3 8

Sample Output 1

4
4
3
2
3
3
4