You are given an array of \(N\) integers. A function is defined as follows:   .

\(F(i, j) = G.C.D(A_i, A_{i+1}, ... A_j)\)

You are also given \(Q\) queries of the form \(L\ R\). For every query, you must answer the value:

 \(\sum_{i = L}^{R}\sum_{j = i + 1}^{R} F(i, j)\)
 

Input format

• First line: Two integers \(N\) and \(M\) denoting the number of elements in the array and queries
• Next line: \(N\) integers, \(A_i\)
• Next \(M\) lines: Query in the mentioned format 

Output format
For each query print an integer in a new line denoting the answer to that query.

Constraints
\(1 \leq N, M \leq 2\times10^5\)
\( 1\leq A_i \leq 3\times10^8\)
\(1 \leq L \leq R \leq N\)