Bình có một dãy số nguyên dương. Bình muốn tìm đoạn con liên tiếp dài nhất sao cho ước số chung lớn nhất (GCD) của tất cả các phần tử trong đoạn đó ít nhất bằng \(2\).

Hãy giúp Bình trả lời \(Q\) truy vấn, mỗi truy vấn cho biết độ dài đoạn con dài nhất thỏa mãn trong đoạn \([l, r]\).

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ó đoạn nào, in ra \(0\).

Ví dụ

Input:

6 3
12 6 5 8 3 9
1 6
2 5
3 6

Output:

2
1
2