Count Multiples Pairs Query

You are given a sequence \(a = [a_1, a_2, \dots, a_n]\) of positive integers. You have to answer \(q\) queries. For each query, you are given an interval \([l, r]\). For the subarray \(a_l, a_{l+1}, \dots, a_r\), count the number of ordered pairs \((i,j)\) (with \(l \le i,j \le r\)) such that \(a_i\) is a multiple of \(a_j\), i.e. \(a_i \bmod a_j = 0\).

Note: Pairs where \(i = j\) are also counted.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \leq n,q \leq 10^5)\) — the length of the sequence and the number of queries. The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\). Each of the next \(q\) lines contains two integers \(l\) and \(r\) \( (1 \leq l \leq r \leq n)\) representing a query.

It is guaranteed that the input is such that a solution with an \(O(n^2)\) approach per query will pass for the given test cases.

outputFormat

For each query, output a single integer representing the number of ordered pairs \((i,j)\) in the subarray \([l, r]\) such that \(a_i \bmod a_j = 0\).

sample

5 2
2 4 8 2 16
1 3
2 5

6
10