Bạn được cung cấp một dãy số nguyên dương \(A\) gồm \(N\) phần tử.

Với mỗi số nguyên \(A_i\) bạn cần đếm số lượng ước nguyên dương của nó.

Ta có \(Q\) truy vấn, mỗi truy vẫn gồm hai số nguyên dương \(l, r\) \((1 \leq l \leq r \leq N)\). Hãy in ra tổng số lượng ước của mỗi số từ đoạn \(A_l, A_{l + 1}, \ldots, A_r\).

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\).
• Dòng thứ \(2\) gồm \(N\) số nguyên dương \(A_1, A_2, \ldots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(l, r\).

Output

• Gồm \(Q\) dòng, mỗi dòng là câu trả lời của từng truy vấn theo thứ tự tương ứng.

Example

5 2
1 2 3 4 5
1 5
2 4

10
7

4 1
9 25 4 2
1 3

9

Scoring

• Subtask \(1\) (\(40\%\) số điểm):
  • \(1 \leq N, Q \leq 100\)
  • \(1 \leq A_i \leq 100\)
• Subtask \(2\) (\(20\%\) số điểm):
  • \(1 \leq N, Q \leq 1000\)
  • \(1 \leq A_i \leq 10000\)
• Subtask \(3\) (\(20\%\) số điểm):
  • \(1 \leq N, Q \leq 10^5\)
  • \(1 \leq A_i \leq 10^6\)
• Subtask \(4\) (\(20\%\) số điểm):
  • \(1 \leq N, Q \leq 10^6\)
  • \(1 \leq A_i \leq 10^7\)