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$