Madeline's Dream

In Madeline's dream, the border of her city is constructed from numerous cosmic fragments. Each cosmic fragment has an energy value, and since their sizes vary, their energy values differ. Madeline enjoys weaving through these fragments. Every time she selects two cosmic fragments (they can be the same), she obtains a pleasure value that is equal to the greatest common divisor (GCD) of their energy values.

The cosmic fragments form a sequence \(a_1, a_2, \cdots, a_n\). Each time, Madeline chooses a subarray \([l, r]\), and for every ordered pair \((u, v)\) in this interval (where both \(u\) and \(v\) are elements in the subarray), she experiences one jump. Formally, the pleasure value she gains from the subarray is:

When Madeline was abruptly awakened from her dream, all the cosmic fragments vanished. She only vaguely remembers the intervals she selected. Now, she has turned to you, a coding genius, to help restore the pleasure values from her dream. Given the intervals she chose, compute the sum of GCDs for each queried subarray.

inputFormat

The first line contains two integers \(n\) and \(q\) --- the number of cosmic fragments and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the energy values of the cosmic fragments.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) (1-indexed), representing a query on the subarray from index \(l\) to \(r\).

outputFormat

For each query, output the pleasure value defined as:

Print each answer on a new line.

sample

3 2
1 2 3
1 1
1 3

1
12