Tèo có một dãy số nguyên dương. Với mỗi truy vấn \((l, r)\), Tèo muốn tìm độ dài của đoạn con dài nhất bắt đầu từ \(l\) sao cho tất cả các phần tử trong đoạn con đó đều chia hết cho phần tử đầu tiên \(A_l\).

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.

Ví dụ

Input:

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

Output:

3
2
3