SOLVE
LATER
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,
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
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\)
For the first query, there are no coprime-twin pairs in this range.
For the second query, \([2, 4]\) is the only subarray having score 1 (because of the coprime-twin pair \((4, 8)\) ). All other subarrays have score 0.
For the third query, the subarrays and their scores are :
\([1, 1], [2, 2], [2, 3], [3, 3], [3, 4], [4, 4] \ \ \ => \ \ \ score = 0\)
\([1, 2], [1, 3], [2, 4] \ \ \ => \ \ \ score = 1\)
\([1, 4] \ \ \ => \ \ \ score = 3\)
The sum of the scores is therefore, \(6\).
The answers to the remaining queries can be found similarly.