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\)