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.

×
G. Common Divisor Graph

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider a sequence of distinct integers $$$a_1, \ldots, a_n$$$, each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than $$$1$$$.

There are $$$q$$$ queries, in each query, you want to get from one given node $$$a_s$$$ to another $$$a_t$$$. In order to achieve that, you can choose an existing value $$$a_i$$$ and create new value $$$a_{n+1} = a_i \cdot (1 + a_i)$$$, with edges to all values that are not coprime with $$$a_{n+1}$$$. Also, $$$n$$$ gets increased by $$$1$$$. You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that $$$a_t$$$ is reachable from $$$a_s$$$?

Queries are independent. In each query, you start with the initial sequence $$$a$$$ given in the input.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 150\,000$$$, $$$1 \leq q \leq 300\,000$$$) — the size of the sequence and the number of queries.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$2 \leq a_i \leq 10^6$$$, $$$a_i \neq a_j$$$ if $$$i \ne j$$$).

The $$$j$$$-th of the following $$$q$$$ lines contains two distinct integers $$$s_j$$$ and $$$t_j$$$ ($$$1 \leq s_j, t_j \leq n$$$, $$$s_j \neq t_j$$$) — indices of nodes for $$$j$$$-th query.

Output

Print $$$q$$$ lines. The $$$j$$$-th line should contain one integer: the minimum number of new nodes you create in order to move from $$$a_{s_j}$$$ to $$$a_{t_j}$$$.

Examples

Input

3 3 2 10 3 1 2 1 3 2 3

Output

0 1 1

Input

5 12 3 8 7 6 25 1 2 1 3 1 4 1 5 2 1 2 3 2 4 2 5 3 1 3 2 3 4 3 5

Output

0 1 0 1 0 1 0 1 1 1 1 2

Note

In the first example, you can first create new value $$$2 \cdot 3 = 6$$$ or $$$10 \cdot 11 = 110$$$ or $$$3 \cdot 4 = 12$$$. None of that is needed in the first query because you can already get from $$$a_1 = 2$$$ to $$$a_2 = 10$$$.

In the second query, it's optimal to first create $$$6$$$ or $$$12$$$. For example, creating $$$6$$$ makes it possible to get from $$$a_1 = 2$$$ to $$$a_3 = 3$$$ with a path $$$(2, 6, 3)$$$.

In the last query of the second example, we want to get from $$$a_3 = 7$$$ to $$$a_5 = 25$$$. One way to achieve that is to first create $$$6 \cdot 7 = 42$$$ and then create $$$25 \cdot 26 = 650$$$. The final graph has seven nodes and it contains a path from $$$a_3 = 7$$$ to $$$a_5 = 25$$$.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/03/2022 04:53:47 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|