Cho dãy số nguyên ~A~ gồm ~n~ số nguyên: ~a_1, a_2, \dots, a_n~.

Một đoạn con gồm các phần tử liên tiếp của ~A~ từ vị trí ~s~ đến vị trí ~t~ (~s \le t~) được gọi là đoạn con đặc biệt nếu thỏa mãn điều kiện:

~a_s \cdot a_{s+1} \cdot \dots \cdot a_t = \operatorname{lcm}(a_s, a_{s+1}, \dots, a_t)~

với ~\operatorname{lcm}(a_s, a_{s+1}, \dots, a_t)~ là bội chung nhỏ nhất của ~a_s, a_{s+1}, \dots, a_t~.

Có ~q~ truy vấn, truy vấn thứ ~i~ là: cho hai số nguyên ~l_i~ và ~r_i~, hãy chia đoạn ~a_{l_i}, a_{l_i+1}, \dots, a_{r_i}~ thành ít nhất các đoạn con đặc biệt.

Yêu cầu: Với mỗi truy vấn, hãy tìm số đoạn con đặc biệt ít nhất.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 10^5~);

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^5~);

• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~ và ~r_i~ (~1 \le l_i \le r_i \le n~).

Output

Gồm ~q~ dòng, dòng thứ ~i~ ghi kết quả của truy vấn thứ ~i~.

Scoring

Sample Input 1

5 2
2 3 10 7 5
2 4
3 5

Sample Output 1

1
2

Notes

Truy vấn 1: các phần tử ~3, 10, 7~ có tích và bội chung nhỏ nhất cùng bằng ~210~, nên chia thành số đoạn con đặc biệt ít nhất là ~1~.

Truy vấn 2: các phần tử ~10, 7, 5~ có thể chia thành ít nhất ~2~ đoạn con đặc biệt thỏa mãn.