A pair of distinct positive integers $(a, b)$ is said to be a coprime-twin pair, if for all positive integers $x$, both $a$ and $b$ are coprime to $x$ or both $a$ and $b$ are not coprime to $x$. Formally, 2 distinct positive integers $a$ and $b$ can form a coprime-twin pair if and only if $S(a) = S(b)$, where $S(x)$ denotes the set of all positive integers that are coprime to $x$. For example,

• $(2, 4)$ and $(18, 24)$ are coprime-twin pairs.
• $(1, 2)$ and $(4,6)$ are not coprime-twin pairs.
• $(3, 3)$ is not a coprime-twin pair because a coprime-twin pair must consist of distinct integers.

The score of a sequence $a_1, a_2, ..., a_n$ is the number of indices $i, j$ such that $1 \le i < j \le n$ and the pair $(a_i, a_j)$ forms a coprime-twin pair.

You are given an array $A$ of $N$ positive integers and $Q$ queries of the form $L, R$. For each query, determine the sum of the scores of all subarrays that completely lie within the range $[L, R]$ (both inclusive).

Note: A subarray is a contiguous non-empty segment of the array. If a subarray completely lies within the range $[L, R]$, then it means that both its endpoints lie within this range.

Input format

• First line: Two space-separated integers $N$ and $Q$ where $N$ denotes the size of the array $A$ and $Q$ denotes the number of queries respectively
• Next line: $N$ space-separated integers that represent the array $A$
• Next $Q$ lines: Two space-separated integers $L \ R$

Output format

For each query, print the answer to the query in a new line as mentioned in the problem statement.

Constraints

$1 \le N, Q \le 10^5$

$1 \le A_i \le 10^6$

$1 \le L \le R \le N$