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, \dots, 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}, \dots, a_r~.

Yêu cầu: Hãy tính tổng số lượng ước của các số trong đoạn ~[l, r]~ cho mỗi học sinh.

Input

• 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, \dots, 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~).

Output

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

Sample Input 1

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

Sample Output 1

5
10
11