Với mọi số tự nhiên \(m\ (m\ \geq \ 2)\) đều có ít nhất hai ước dương khác nhau đó là 1 và chính nó. Ta kí hiệu \(s(m)\) là tổng của hai ước dương nhỏ nhất (khác nhau) của \(m\).

Ví dụ: \(s(3)\ = \ 1 + 3\ = \ 4;\ s(8)\ = \ 1 + 2\ = \ 3\).

Cho dãy số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) và cặp chỉ số \(i,\ j\ (1\ \leq \ i\ \leq \ j\ \leq \ n)\).

Yêu cầu: Tính tổng \(s(a_{i})\ + \ s(a_{i} + 1)\ + \ \ldots\ + \ s(a_{j})\).

Dữ liệu vào:

+ Dòng 1 ghi hai số nguyên dương \(n\) và \(T\) tương ứng là số số hạng của dãy và số testcase.

+ Dòng 2 ghi \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\).

+ T dòng tiếp theo, mỗi dòng là một testcase tương ứng là một cặp chỉ số i, j (1 ≤ i ≤ j ≤ n).

Kết quả: gồm T dòng, mỗi dòng là kết quả của testcase tương ứng.

Ví dụ:

Giới hạn:

+ 30% số test ứng với \(n\ \leq \ 100\) và \(T\ \leq \ 10,\ 2\ \leq \ a_{i}\ \leq \ 10^{7}\);

+ 30% số test khác ứng \(n\ \leq \ 100000\), \(T\ \leq \ 1000\) và \(2\ \leq \ a_{i}\ \leq \ 10^{4}\);

+ 40% số test còn lại ứng với \(n\ \leq \ 100000,\ T\ \leq \ 10^{4};\ 2\ \leq \ a_{i}\ \leq \ 10^{7}\).