Victorique gives you a sequence $a$, and for each query, you are given an interval $[l, r]$.

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

Input

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

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

The following $m$ lines each contain two integers $l$ and $r$, representing a query.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 1

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

Output 1

1
3
10

Subtasks

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

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