Với mọi số tự nhiên ~m~ ~(m ≥ 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,…,a_n~ và cặp chỉ số ~i,j~ ~(1 ≤ i ≤ j ≤ n)~.

Yêu cầu: Tính tổng ~s(a_i) + s(a_{i+1} ) + … + 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,… ,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.

**Ràng buộc: **

• 30% số test ứng với ~𝑛 ≤ 100~ và ~𝑇 ≤ 10, 2 ≤ 𝑎_𝑖 ≤ 10^7~;
• 30% số test khác ứng ~𝑛 ≤ 100000, 𝑇 ≤ 1000~ và ~2 ≤ 𝑎_𝑖 ≤ 10^4~;
• 40% số test còn lại ứng với ~𝑛 ≤ 100000, 𝑇 ≤ 10^4; 2 ≤ 𝑎_𝑖 ≤ 10^7~.

Ví dụ:

Input

5  3
2  3  8  9  100
1  3
4  4
3  5 

Output

10
4
10