Consider a sequence of distinct integers a_1, …, 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 ⋅ (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 ≤ n ≤ 150 000, 1 ≤ q ≤ 300 000) — the size of the sequence and the number of queries.

The second line contains n distinct integers a_1, a_2, …, a_n (2 ≤ a_i ≤ 10^6, a_i ≠ a_j if i ≠ j).

The j-th of the following q lines contains two distinct integers s_j and t_j (1 ≤ s_j, t_j ≤ n, s_j ≠ 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 ⋅ 3 = 6 or 10 ⋅ 11 = 110 or 3 ⋅ 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).

<image>

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 ⋅ 7 = 42 and then create 25 ⋅ 26 = 650. The final graph has seven nodes and it contains a path from a_3 = 7 to a_5 = 25.

Difficulty: VERY_HARD
Tags: Graph algorithms

Constructive algorithms

String algorithms

Complete search

Number theory

Mathematics

Spanning trees
Skill types: Complete search

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def connected_components(n, graph):
	(components, visited) = ([], [False] * n)

	def dfs(start):
		(component, stack) = ([], [start])
		while stack:
			start = stack[-1]
			if visited[start]:
				stack.pop()
				continue
			else:
				visited[start] = True
				component.append(start)
			for i in graph[start]:
				if not visited[i]:
					stack.append(i)
		return component
	for i in range(n):
		if not visited[i]:
			components.append(dfs(i))
	return components

def Sieve(limit=10 ** 6):
	isPrime = [1] * (limit + 1)
	isPrime[0] = isPrime[1] = 0
	for i in range(2, limit + 1):
		if isPrime[i] != 1:
			continue
		for j in range(i * i, limit + 1, i):
			isPrime[j] = i
	return isPrime
isPrime = Sieve(10 ** 6 + 2)

def prime_factors(n):
	if n < 2:
		return []
	result = []
	while isPrime[n] > 1:
		y = isPrime[n]
		result += [y]
		while n % y == 0:
			n //= y
	if n != 1:
		result += [n]
	return result
for _ in range(int(input()) if not True else 1):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	graph = [[] for i in range(n)]
	px = {}
	for i in range(n):
		for p in prime_factors(a[i]):
			if p not in px:
				px[p] = i
			else:
				graph[i] += [px[p]]
				graph[px[p]] += [i]
	cp = connected_components(n, graph)
	comp_num = [0] * n
	for i in range(1, len(cp)):
		for j in cp[i]:
			comp_num[j] = i
	st2 = set()
	for i in range(len(cp)):
		for j in cp[i]:
			y = set()
			for prime in prime_factors(a[j] + 1):
				if prime in px:
					st2.add((i, comp_num[px[prime]]))
					y.add(comp_num[px[prime]])
			for y1 in y:
				for y2 in y:
					if y1 != y2:
						st2.add((y1, y2))
	for __ in range(q):
		(x, y) = map(int, input().split())
		x -= 1
		y -= 1
		if comp_num[x] == comp_num[y]:
			print(0)
			continue
		(p, q) = (comp_num[x], comp_num[y])
		if (p, q) in st2 or (q, p) in st2:
			print(1)
			continue
		print(2)


import itertools
from sys import stdin

def input():
	return next(stdin)[:-1]

def readline():
	return map(int, input().split())
primes = [2]
for q in range(3, 10 ** 3, 2):
	if all((q % p for p in primes)):
		primes.append(q)

def prime_divisors(n):
	for p in primes:
		if p * p > n:
			break
		if n % p == 0:
			yield p
			while n % p == 0:
				n //= p
	if n > 1:
		yield n

def test_prime_divisors():
	assert list(prime_divisors(6)) == [2, 3]
	assert list(prime_divisors(9)) == [3]
	assert list(prime_divisors(10)) == [2, 5]
	assert list(prime_divisors(7)) == [7]
	assert list(prime_divisors(997)) == [997]
	assert list(prime_divisors(1009)) == [1009]

class DSU:

	def __init__(self):
		self.p = list(range(10 ** 6))

	def _get_root(self, a):
		while self.p[a] != a:
			a = self.p[a]
		return a

	def __setitem__(self, a, b):
		assert b <= a
		r = self._get_root(b)
		while a != r:
			(self.p[a], a) = (r, self.p[a])

	def __getitem__(self, a):
		self[a] = a
		return self.p[a]

def main():
	(n, q) = readline()
	a = list(readline())
	queries = (readline() for __ in range(q))
	min_divisor = list()
	dsu = DSU()
	for ai in a:
		(p, *rest) = prime_divisors(ai)
		min_divisor.append(p)
		for q in rest:
			dsu[q] = p
	close = set()
	for (ai, p) in zip(a, min_divisor):
		group = sorted({dsu[p]} | {dsu[q] for q in prime_divisors(ai + 1)})
		close.update(itertools.combinations(group, 2))
	for (p, q) in close:
		assert p < q
	for (s, t) in queries:
		p = dsu[min_divisor[s - 1]]
		q = dsu[min_divisor[t - 1]]
		(p, q) = sorted((p, q))
		if p == q:
			print(0)
		elif (p, q) in close:
			print(1)
		else:
			print(2)
main()


import itertools
from collections import defaultdict
from sys import stdin

def input():
	return next(stdin)[:-1]

def readline():
	return map(int, input().split())
primes = [2]
for q in range(3, 10 ** 3, 2):
	if all((q % p for p in primes)):
		primes.append(q)

def prime_divisors(n, primes=primes):
	ret = []
	for p in primes:
		if p * p > n:
			break
		(q, r) = divmod(n, p)
		if not r:
			ret.append(p)
		while not r:
			n = q
			(q, r) = divmod(n, p)
	if n > 1:
		ret.append(n)
	return ret

def test_prime_divisors():
	assert list(prime_divisors(6)) == [2, 3]
	assert list(prime_divisors(9)) == [3]
	assert list(prime_divisors(10)) == [2, 5]
	assert list(prime_divisors(7)) == [7]
	assert list(prime_divisors(997)) == [997]
	assert list(prime_divisors(1009)) == [1009]

class DSU:
	__slots__ = ('p',)

	def __init__(self):
		self.p = list(range(10 ** 6))

	def _get_root(self, a):
		while self.p[a] != a:
			a = self.p[a]
		return a

	def __setitem__(self, a, b):
		assert b <= a
		r = self._get_root(b)
		while a != r:
			(self.p[a], a) = (r, self.p[a])

	def __getitem__(self, a):
		self[a] = a
		return self.p[a]

def main():
	(n, q) = readline()
	a = list(readline())
	queries = (readline() for __ in range(q))
	min_divisor = list()
	dsu = DSU()
	for ai in a:
		(p, *rest) = prime_divisors(ai)
		min_divisor.append(p)
		for q in rest:
			dsu[q] = p
	for i in range(len(dsu.p)):
		dsu[i]
	dsu = dsu.p
	one = list()
	available = defaultdict(set)
	for (ai, p) in zip(a, min_divisor):
		p = dsu[p]
		components = sorted(set((dsu[q] for q in prime_divisors(ai + 1))))
		if p != dsu[2]:
			available[p].update(components)
		one.extend(itertools.combinations(components, 2))
	one = set(one)
	for (p, q) in one:
		assert p < q

	def av(p, q):
		return p in available[q]
	for (s, t) in queries:
		p = dsu[min_divisor[s - 1]]
		q = dsu[min_divisor[t - 1]]
		(p, q) = sorted((p, q))
		if p == q:
			print(0)
		elif dsu[2] in (p, q) or av(p, q) or av(q, p) or ((p, q) in one):
			print(1)
		else:
			print(2)
main()


import itertools
from sys import stdin

def input():
	return next(stdin)[:-1]

def readline():
	return map(int, input().split())
primes = [2]
primes.extend((q for q in range(3, 10 ** 3, 2) if all((q % p for p in primes))))

def prime_divisors(n):
	for p in primes:
		if p * p > n:
			break
		if n % p == 0:
			yield p
			while n % p == 0:
				n //= p
	if n > 1:
		yield n

class DSU:

	def __init__(self):
		self.p = dict()

	def _get_root(self, a):
		while a in self.p:
			a = self.p[a]
		return a

	def __setitem__(self, a, b):
		r = self._get_root(b)
		while a != r:
			(self.p[a], a) = (r, self.p.get(a, a))

	def __getitem__(self, a):
		self[a] = a
		return self.p.get(a, a)

def main():
	(n, q) = readline()
	a = list(readline())
	queries = (readline() for __ in range(q))
	min_divisor = list()
	dsu = DSU()
	for ai in a:
		(p, *rest) = prime_divisors(ai)
		min_divisor.append(p)
		for q in rest:
			dsu[q] = p

	def sorted_tuple(t):
		return tuple(sorted(t))
	one = set()
	for (ai, p) in zip(a, min_divisor):
		new_node = {dsu[p], *(dsu[q] for q in prime_divisors(ai + 1))}
		one.update(map(sorted_tuple, itertools.combinations(new_node, 2)))
	for (s, t) in queries:
		p = dsu[min_divisor[s - 1]]
		q = dsu[min_divisor[t - 1]]
		if p == q:
			print(0)
		elif sorted_tuple((p, q)) in one:
			print(1)
		else:
			print(2)
main()


from collections import defaultdict
from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

class DisjointUnionSet:

	def __init__(self, size):
		self.parent = list(range(size))
		self.rank = [0] * size

	def find_set(self, v):
		if v == self.parent[v]:
			return v
		self.parent[v] = self.find_set(self.parent[v])
		return self.parent[v]

	def union_sets(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		if a != b:
			if self.rank[a] < self.rank[b]:
				(a, b) = (b, a)
			self.parent[b] = a
			if self.rank[a] == self.rank[b]:
				self.rank[a] += 1

def main():
	(n, q) = map(int, input().split())
	aa = [int(a) for a in input().split()]
	mxaa = max(aa)
	pf = [set() for _ in range(mxaa + 2)]
	for i in range(2, mxaa + 2):
		if not pf[i]:
			for j in range(i, mxaa + 2, i):
				pf[j].add(i)
	dus = DisjointUnionSet(mxaa + 2)
	for a in aa:
		for p in pf[a]:
			dus.union_sets(a, p)
	a1p = defaultdict(set)
	for a in aa:
		s1 = {dus.find_set(p) for p in pf[a + 1]}
		a1p[dus.find_set(a)] |= s1
		for s in s1:
			for t in s1:
				if s != t:
					a1p[s].add(t)
	for _ in range(q):
		(s, t) = map(int, input().split())
		ss = dus.find_set(aa[s - 1])
		ts = dus.find_set(aa[t - 1])
		if ss == ts:
			print(0)
		elif ss in a1p[ts] or ts in a1p[ss]:
			print(1)
		else:
			print(2)
main()