Given a permutation $p$ of length $n$, you are asked to answer $m$ queries, each query can be represented as a pair $(l ,r )$, you need to find the number of pair$(i ,j)$ such that $l \le i < j \le r$ and $\min(p_i,p_j) = \gcd(p_i,p_j )$.
There is two integers $n(1 \le n \le 10^5)$, $m(1 \le m \le 10^5)$ in the first line, denoting the length of $p$ and the number of queries.
In the second line, there is a permutation of length $n$, denoting the given permutation $p$. It is guaranteed that $p$ is a permutation of length $n$.
For the next $m$ lines, each line contains two integer $l_i$ and $r_i(1 \le l_i \le r_i \le n)$, denoting each query.
For each query, print a single line containing only one integer which denotes the number of pair$(i,j)$.
3 2 1 2 3 1 3 2 3