Cho dãy số gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~. Có ~Q~ truy vấn, mỗi truy vấn cho hai số nguyên ~l~ và ~r~ có ý nghĩa: đếm số cặp chỉ số ~(i, j)~ sao cho ~l\le i, j\le r~ và ~a_i~ chia hết cho ~a_j~ (hai cặp chỉ số ~(i, j)~ và ~(j, i)~ là khác nhau).

INPUT

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ ~(N, Q \le 10^5)~ là số lượng phần tử và số lượng truy vấn;
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_i \ (a_i\le 10^5; \ 1\le i\le N)~ mô tả dãy số;
• ~Q~ dòng sau, mỗi dòng gồm hai số nguyên dương ~l~ và ~r~ ~(1\le l\le r\le N)~ mô tả truy vấn.

OUTPUT

~Q~ dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng.

SAMPLE INPUT

5 2
3 1 3 3 4
2 4
1 5

SAMPLE OUTPUT

7
15

Ở truy vấn đầu tiên có các cặp chỉ số thoả mãn là: ~(2, 2), (3, 3), (4, 4), (3, 2), (4, 2), (3, 4), (4, 3)~

SUBTASKS

• Có ~20\%~ số test ứng với ~20\%~ số điểm thoả mãn: ~N, Q \le 10^2~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm thoả mãn: ~N \le 10^4; \ Q\le 10^2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~N \le 10^5; \ Q\le 10^2~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm thoả mãn: dãy số ~a_1, a_2, \dots, a_N~ là hoán vị từ ~1~ đến ~N~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm thoả mãn: ~l = 1~;
• ~15\%~ số test khác ứng với ~15\%~ số điểm không có ràng buộc gì thêm.