Cho dãy ~n~ số tự nhiên ~a_1,a_2,\ldots,a_n~. Với mỗi truy vấn ~l,r~, cần tính tổng số lượng ước của các số trong đoạn ~a_l,a_{l+1},\ldots,a_r~.

Input

Dòng đầu chứa hai số ~n,q~ ~(1 \le n,q \le 10^6)~.

Dòng thứ hai chứa ~n~ số ~a_i~ ~(1 \le a_i \le 10^6)~.

~q~ dòng tiếp theo, mỗi dòng chứa hai số ~l,r~ ~(1 \le l \le r \le n)~.

Output

In ra kết quả của mỗi truy vấn trên một dòng.

Subtask

• Subtask 1: ~n\cdot q \le 10^4~, ~a_i \le 100~.
• Subtask 2: ~n\cdot q \le 10^4~.
• Subtask 3: Không có ràng buộc bổ sung.

Ví dụ

5 3
1 3 2 6 2
1 3
2 5
1 5

5
10
11