Marisa muốn nấu ăn bằng một số loại thảo mộc cô mới hái được. Mỗi loại có một độ độc nhất định, tuy vậy nếu kết hợp các loại thảo mộc mà tích độ độc của chúng bằng bội chung nhỏ nhất của chúng thì độc tố sẽ biến mất.

Có ~q~ ngày, ngày thứ ~q~ Marisa muốn chọn các loại thảo mộc từ vị trí ~l~ đến vị trí ~r~ để nấu ăn, mỗi món ăn sẽ được nấu từ các thảo mộc liên tiếp và phải không có độc. Hãy giúp cô tính số lượng món ăn ít nhất có thể nấu được vì nhiều quá cô sẽ không ăn hết.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~n, q~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_i~ là độ độc của món ăn thứ ~i~.
• ~q~ dòng tiếp theo gồm 2 số ~l_i, r_i~ .

Output:

• Gồm ~q~ số nguyên dương là đáp án của ~q~ ngày.

Sample Test:

Input

5 2
2 3 10 7 5
2 4
3 5

Output:

1
2

Giải thích:

• Ở test 1, 3 số 3 10 7 có tích bằng với bội chung nhỏ nhất là 210 nên có thể chia thành 1 đoạn.
• Ở test 2, có thể chia thành đoạn 10 và 7 5, không thể có kết quả nhỏ hơn.

Giới hạn:

• Trong mọi test ~a_i \le 10^5~.
• 25% số điểm: ~n, q \le 100~.
• 25% số điểm: ~n, q \le 1000~.
• 25% số điểm: ~a_i~ là các số nguyên tố.
• 25% số điểm: ~n, q \le 10^5~.