C. Frosted Highway
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As the southern US prepares for the weekend's ice freeze, and the City of Austin has hired a surveyor to help you ensure all the highway markers are set up properly for drivers. Unfortunately the surveyor is nowhere near Austin, so the best way they can help is a virtual Zoom conference to ensure all the highway markers are set up properly.

The highway has $$$n$$$ markers indexed from $$$1$$$ to $$$n$$$, and a marker of height $$$h_i$$$ is "stable" if $$$\gcd(h_i, i) = 1$$$. The markers do not necessarily have to all be stable, so your surveyor will instead provide you a set of $$$q$$$ queries in the form $$$(l,r)$$$, and you need to respond ASAP with how many stable markers are in the interval $$$[l,r]$$$ (inclusive). Get this done as soon as possible to prevent overfreezing!

Input

The first line contains two numbers, $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^4$$$), the number of markers on the highway and the number of queries respectively. The second line contains the array $$$h$$$ of $$$n$$$ integers, where $$$h_i$$$ denotes the height of the $$$i$$$th marker ($$$1 \le h_i \le 10^6$$$). The next $$$q$$$ lines each contain two numbers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le n$$$), denoting the query as described in the problem statement.

Output

Print $$$q$$$ integers, where the $$$i$$$th integer represents the answer to query $$$i$$$: the number of stable markers between $$$l_i$$$ and $$$r_i$$$ inclusive.

Example
Input
5 3
8 6 5 4 10
3 4
2 3
1 5
Output
1
1
2