Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Cut

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $$$a$$$ of length $$$n$$$ written on it, and then he does the following:

- he picks a range $$$(l, r)$$$ and cuts the subsegment $$$a_l, a_{l + 1}, \ldots, a_r$$$ out, removing the rest of the array.
- he then cuts this range into multiple subranges.
- to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM).

Formally, he partitions the elements of $$$a_l, a_{l + 1}, \ldots, a_r$$$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $$$q$$$ independent ranges $$$(l, r)$$$, tell Baby Ehab the minimum number of subarrays he needs.

Input

The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the length of the array $$$a$$$ and the number of queries.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the array $$$a$$$.

Each of the next $$$q$$$ lines contains $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of this query's interval.

Output

For each query, print its answer on a new line.

Example

Input

6 3 2 3 10 7 5 14 1 6 2 4 3 5

Output

3 1 2

Note

The first query asks about the whole array. You can partition it into $$$[2]$$$, $$$[3,10,7]$$$, and $$$[5,14]$$$. The first subrange has product and LCM equal to $$$2$$$. The second has product and LCM equal to $$$210$$$. And the third has product and LCM equal to $$$70$$$. Another possible partitioning is $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.

The second query asks about the range $$$(2,4)$$$. Its product is equal to its LCM, so you don't need to partition it further.

The last query asks about the range $$$(3,5)$$$. You can partition it into $$$[10,7]$$$ and $$$[5]$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2021 17:46:50 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|