E. Erase the Primes
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A positive integer is called good if it is divisible by at least two different prime numbers.

For a sequence of positive integers, you may apply zero or more operations on it. Each operation consists of removing any two elements from the sequence and appending their product to the end. The cost of a sequence is defined as the minimum number of operations required to make all of its elements good, or $$$-1$$$ if it's impossible to do so.

Given an sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, you will be asked $$$q$$$ queries about it. In each query, two indices $$$l$$$ and $$$r$$$ are given, and you should find the cost of the subsequence $$$a_l, a_{l+1}, \dots, a_{r-1}, a_r$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \times 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$).

Then $$$q$$$ lines follow. Each of these lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) describing a query.

Output

For each query, print one number — the answer to the query.

Example
Input
8 5
2 8 3 5 1 9 42 3
5 5
1 3
6 8
1 8
2 7
Output
-1
2
2
4
3