Số tự nhiên ~y~ chia hết cho số tự nhiên ~x~ thì ~x~ được gọi là ước của ~y~.

Trong một giờ học môn Toán, sau khi học xong kiến thức về ước của số tự nhiên, để củng cố kiến thức cho học sinh, thầy giáo tổ chức một trò chơi như sau:

Cho trước dãy ~\{a\}~ gồm ~n~ số tự nhiên ~a_1, a_2, \ldots, a_n~. Có ~q~ học sinh tham gia trò chơi. Với mỗi học sinh tham gia trò chơi, thầy sẽ đưa ra hai số tự nhiên ~l~ và ~r~ (~1 \le l \le r \le n~). Nhiệm vụ của học sinh đó là tính tổng số lượng ước của các số tự nhiên trong dãy ~a_l, a_{l+1}, \ldots, a_r~.

Yêu cầu: hãy đưa ra kết quả của ~q~ học sinh tham gia trò chơi.

Dữ liệu

Nhập từ bàn phím gồm:

• Dòng đầu tiên gồm hai số tự nhiên ~n~ và ~q~ (~1 \le n, q \le 10^6~) tương ứng là số lượng số trong dãy ~\{a\}~ và số học sinh tham gia trò chơi;
• Dòng thứ hai gồm ~n~ số tự nhiên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^6~);
• ~q~ dòng tiếp theo, mỗi dòng gồm hai số tự nhiên ~l~ và ~r~ (~1 \le l \le r \le n~).

Kết quả

In ra màn hình kết quả tính được của ~q~ học sinh, mỗi kết quả in trên một dòng.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

5
10
11

Giải thích: Với học sinh thứ nhất: ~l = 1, r = 3~, học sinh cần tính tổng số lượng ước của dãy các số ~a_1, a_2, a_3~. Ta có: ~a_1 = 1~ có 1 ước (1), ~a_2 = 3~ có 2 ước (1, 3), ~a_3 = 2~ có 2 ước (1, 2) ~\to~ Tổng số lượng ước là: ~1 + 2 + 2 = 5~.

Giới hạn

• Subtask 1 (40% số test): ~n \times q \le 10^4~, ~a_i \le 100~;
• Subtask 2 (40% số test): ~n \times q \le 10^4~;
• Subtask 3 (20% số test): Không có ràng buộc gì thêm.