Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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

H. Make Square

time limit per test

7 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputWe call an array $$$b_1, b_2, \ldots, b_m$$$ good, if there exist two indices $$$i < j$$$ such that $$$b_i \cdot b_j$$$ is a perfect square.

Given an array $$$b_1, b_2, \ldots, b_m$$$, in one action you can perform one of the following:

- multiply any element $$$b_i$$$ by any prime $$$p$$$;
- divide any element $$$b_i$$$ by prime $$$p$$$, if $$$b_i$$$ is divisible by $$$p$$$.

Let $$$f(b_1, b_2, \ldots, b_m)$$$ be the minimum number of actions needed to make the array $$$b$$$ good.

You are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ and $$$q$$$ queries of the form $$$l_i, r_i$$$. For each query output $$$f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 194\,598$$$, $$$1 \le q \le 1\,049\,658$$$) — the length of the array and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5\,032\,107$$$) — the elements of the array.

Each of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — the parameters of a query.

Output

Output $$$q$$$ lines — the answers for each query in the order they are given in the input.

Example

Input

10 10

34 37 28 16 44 36 43 50 22 13

1 3

4 8

6 10

9 10

3 10

8 9

5 6

1 4

1 7

2 6

Output

2

0

1

3

0

1

1

1

0

0

Note

In the first query of the first sample you can multiply second number by 7 to get 259 and multiply the third one by 37 to get 1036. Then $$$a_2 \cdot a_3 = 268\,324 = 518^2$$$.

In the second query subarray is already good because $$$a_4 \cdot a_6 = 24^2$$$.

In the third query you can divide 50 by 2 to get 25. Then $$$a_6 \cdot a_8 = 30^2$$$.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 11:52:43 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|