An có một dãy số nguyên dương. Với mỗi truy vấn \((l, r)\), An muốn tìm độ dài của đoạn con liên tiếp dài nhất trong \([l, r]\) sao cho ước số chung lớn nhất (GCD) của toàn bộ đoạn con đó lớn hơn \(1\).

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra độ dài lớn nhất tìm được. Nếu không có, in ra \(0\).

Ví dụ

Input:

7 3
12 6 18 5 10 20 7
1 7
2 5
4 7

Output:

3
2
2