Yaroslav has an array $*p* = *p*_{1}, *p*_{2}, ..., *p*_{*n*}$ $(1 ≤ *p*_{*i*} ≤ *n*)$, consisting of $*n*$ distinct integers. Also, he has $*m*$ queries:

• Query number $*i*$ is represented as a pair of integers $*l*_{*i*}$, $*r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*)$.
• The answer to the query $*l*_{*i*}, *r*_{*i*}$ is the number of pairs of integers $*q*$, $*w*$ $(*l*_{*i*} ≤ *q*, *w* ≤ *r*_{*i*})$ such that $*p*_{*q*}$ is the divisor of $*p*_{*w*}$.

Help Yaroslav, answer all his queries.

Input

The first line contains the integers $*n*$ and $*m*$ $(1 ≤ *n*, *m* ≤ 2·10^{5})$. The second line contains $*n*$ distinct integers $*p*_{1}, *p*_{2}, ..., *p*_{*n*}$ $(1 ≤ *p*_{*i*} ≤ *n*)$. The following $*m*$ lines contain Yaroslav's queries. The $*i*$-th line contains integers $*l*_{*i*}, *r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*)$.

Output

Print $*m*$ integers — the answers to Yaroslav's queries in the order they appear in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.