Description

Victo rica gives you a sequence $a$. Each query gives an interval $[l,r]$.

Count the number of ordered pairs $(i,j)$ such that $l \leq i,j \leq r$ and $a_i$ is a multiple of $a_j$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers, representing the sequence $a$.

Then follow $m$ lines, each containing two integers $l,r$, representing one query.

Output Format

For each query, output one line with one integer, representing the answer.

6 3
1 1 4 5 1 4
1 1
4 5
1 4

1
3
10

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

Constraints: for $100\%$ of the data, $1 \leq n,m,a_i \leq 5 \times 10^5$, $1 \leq l \leq r \leq n$.

Translated by ChatGPT 5