Trong quá trình nghiên cứu, PhuocThien phát hiện rằng mỗi con số \(x\) đều mang một “sức mạnh ẩn” chính là số lượng ước số của nó.

Bạn được cho một số \(N\) và \(Q\) truy vấn.
Mỗi truy vấn yêu cầu tính tổng số lượng ước của các số trong đoạn \([L, R]\).

Input

• Dòng 1: hai số \(N, Q\) \((1 \le N \le 10^6,\ 1 \le Q \le 2 \cdot 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(L, R\) \((1 \le L \le R \le N)\).

Output

• Với mỗi truy vấn, in ra một số nguyên là: \(\sum_{i=L}^{R} d(i)\), trong đó \(d(i)\) là số lượng ước của \(i\).

Ví dụ

5 2
1 3
2 5

5
9

Ràng buộc

• \(1 \le N \le 10^6\).
• \(1 \le Q \le 2 \cdot 10^5\).

Scoring

• Subtask \(1\) (\(30\%\)): \(N \le 10^5\).
• Subtask \(2\) (\(70\%\)): Không có ràng buộc thêm.