This 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}, …, 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)](https://en.wikipedia.org/wiki/Least_common_multiple). 



Formally, he partitions the elements of a_l, a_{l + 1}, …, 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 ≤ n,q ≤ 10^5) — the length of the array a and the number of queries.

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

Each of the next q lines contains 2 integers l and r (1 ≤ l ≤ r ≤ 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].

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Sorting

Amortized analysis

Number theory

Dynamic programming

Data structures


Solutions:
mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from math import gcd
	input = sys.stdin.buffer.readline
	V = 10 ** 5
	minfactor = list(range(V + 1))
	for d in range(2, V + 1):
		for x in range(2, V + 1):
			if d * x > V:
				break
			if minfactor[d * x] == d * x:
				minfactor[d * x] = d
	(N, Q) = map(int, input().split())
	A = [0] + list(map(int, input().split())) + [1]
	N += 1
	M = 1
	seen = [0] * (V + 1)
	r = 1
	nxt_0 = [-1] * (N + 1)
	for l in range(1, N + 1):
		while True:
			if r == N:
				break
			a = A[r]
			d_set = set()
			while a != 1:
				d = minfactor[a]
				d_set.add(d)
				a //= d
			ok = 1
			for d in d_set:
				if seen[d]:
					ok = 0
					break
			if not ok:
				break
			else:
				r += 1
				for d in d_set:
					seen[d] = 1
		nxt_0[l] = r
		a = A[l]
		while a != 1:
			d = minfactor[a]
			seen[d] = 0
			a //= d
	nxt = [[-1] * (N + 1) for _ in range(18)]
	nxt[0] = nxt_0
	for lv in range(1, 18):
		for l in range(1, N + 1):
			nxt[lv][l] = nxt[lv - 1][nxt[lv - 1][l]]
	for _ in range(Q):
		(l, r) = map(int, input().split())
		ans = 0
		for lv in range(17, -1, -1):
			l_new = nxt[lv][l]
			if l_new <= r:
				ans += 1 << lv
				l = l_new
		ans += 1
		print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
_print = print
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')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())
_FAC = 10 ** 5

def prime_sieve(n):
	flag = n % 6 == 2
	sieve = bytearray((n // 3 + flag >> 3) + 1)
	for i in range(1, int(n ** 0.5) // 3 + 1):
		if not sieve[i >> 3] >> (i & 7) & 1:
			k = 3 * i + 1 | 1
			for j in range(k * k // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
			for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
	return sieve

def prime_list(n):
	res = []
	if n > 1:
		res.append(2)
	if n > 2:
		res.append(3)
	if n > 4:
		sieve = prime_sieve(n + 1)
		res.extend((3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not sieve[i >> 3] >> (i & 7) & 1))
	return res
PRIME_FACTORS = [set() for _ in range(_FAC + 1)]
for p in prime_list(_FAC):
	kp = p
	while kp <= _FAC:
		PRIME_FACTORS[kp].add(p)
		kp += p
EXP = _FAC.bit_length() + 1

def main():
	(n, q) = mpint()
	arr = tuple(mpint())
	dp = [[0] * n for _ in range(EXP)]
	i = 0
	st = PRIME_FACTORS[arr[0]].copy()
	for (j, a) in enumerate(arr[1:], 1):
		pf = PRIME_FACTORS[a]
		cp = st & pf
		if cp:
			while cp:
				dp[0][i] = j
				prev_pf = PRIME_FACTORS[arr[i]]
				st -= prev_pf
				cp -= prev_pf
				i += 1
		st |= pf
	while i != n:
		dp[0][i] = n
		i += 1
	for i in range(1, EXP):
		for j in range(n):
			lf = dp[i - 1][j]
			dp[i][j] = n if lf == n else dp[i - 1][lf]
	for _ in range(q):
		(lf, rg) = mpint()
		lf = dp[0][lf - 1]
		ans = 1
		while lf < rg:
			for step in range(1, EXP):
				if dp[step][lf] >= rg:
					ans += 1 << step - 1
					lf = dp[step - 1][lf]
					break
		print(ans)
DEBUG = 0
URL = 'https://codeforces.com/contest/1516/problem/D'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
else:
	if DEBUG != 2:
		(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	if DEBUG:

		def print(*args, **kwargs):
			_print(*args, **kwargs)
			sys.stdout.flush()
	main()


import sys
input = sys.stdin.buffer.readline

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def decompos(num):
	res = []
	if num % 2 == 0:
		res.append(2)
		while num % 2 == 0:
			num //= 2
			if num == 0:
				return []
	for i in range(3, int(num ** 0.5) + 1, 2):
		if i > num:
			break
		if num % i == 0:
			res.append(i)
			while num % i == 0:
				num //= i
	if num > 1:
		res.append(num)
	return res
(n, q) = LI()
prime_last_appear_at = dict()
dp = [[n] * (n + 1) for i in range(18)]
arr = LI()
for i in range(n - 1, -1, -1):
	dp[0][i] = dp[0][i + 1]
	P = decompos(arr[i])
	for p in P:
		if p in prime_last_appear_at:
			dp[0][i] = min(dp[0][i], prime_last_appear_at[p])
		prime_last_appear_at[p] = i
for i in range(1, len(dp)):
	for j in range(n):
		dp[i][j] = dp[i - 1][dp[i - 1][j]]
for _ in range(q):
	(l, r) = LI_()
	cur = l
	res = 1
	for jump in range(len(dp) - 1, -1, -1):
		if dp[jump][cur] <= r:
			res += 1 << jump
			cur = dp[jump][cur]
	print(res)


import sys
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
MX = 10 ** 5 + 1
prime = [[] for i in range(MX)]
for i in range(2, MX):
	if prime[i] == []:
		for j in range(i, MX, i):
			prime[j].append(i)
(n, q) = il()
a = [0] + il()
nxt = [n + 1 for _ in range(MX)]
dp = [[0 for i in range(18)] for j in range(n + 2)]
dp[n + 1][0] = n + 1
for i in range(n, 0, -1):
	dp[i][0] = dp[i + 1][0]
	for j in prime[a[i]]:
		dp[i][0] = min(dp[i][0], nxt[j])
		nxt[j] = i
for i in range(n + 1, 0, -1):
	for j in range(1, 18):
		dp[i][j] = dp[dp[i][j - 1]][j - 1]
for _ in range(q):
	(l, r) = il()
	ans = 1
	for i in range(17, -1, -1):
		if dp[l][i] <= r:
			ans += 1 << i
			l = dp[l][i]
	print(ans)


import sys, os, io
input = sys.stdin.readline
from collections import defaultdict

def sieve(n):
	fact = [float('inf')] * (n + 1)
	fact[1] = 1
	for i in range(2, n + 1):
		if fact[i] == float('inf'):
			j = i
			while j <= n:
				fact[j] = min(fact[j], i)
				j += i
	return fact

def osa_k(n):
	fct = defaultdict(lambda : 0)
	while n > 1:
		fct[facts[n]] += 1
		n //= facts[n]
	return fct.keys()
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
facts = sieve(max(A))
facts = [osa_k(a) for a in A]
nex = {i: i for i in range(N)}
left = 0
lis = defaultdict(lambda : 0)
for fact in facts[0]:
	lis[fact] += 1
for i in range(N):
	nex[i] = left
	for j in range(left + 1, N):
		check = True
		for fact in facts[j]:
			if lis[fact] > 0:
				check = False
				break
		if not check:
			break
		nex[i] = j
		left += 1
		for fact in facts[j]:
			lis[fact] += 1
	for fact in facts[i]:
		lis[fact] -= 1
pos = {i: -1 for i in range(N)}
seg = [[] for _ in range(N)]
indices = [{} for i in range(N)]
for i in range(N):
	if pos[i] == -1:
		p = i
		while p < N - 1 and pos[p] == -1:
			seg[i].append(p)
			indices[i][p] = len(seg[i])
			pos[p] = i
			p = nex[p] + 1
		seg[i].append(p)
		indices[i][p] = len(seg[i])
		if p == N - 1 and pos[p] == -1:
			pos[p] = i
ans = [0] * Q
from bisect import *
for i in range(Q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	start = l
	while r > seg[pos[start]][-1]:
		ans[i] += len(seg[pos[start]]) - indices[pos[start]][start]
		start = seg[pos[start]][-1]
	ind_l = indices[pos[start]][start] - 1
	ind_r = bisect_right(seg[pos[start]], r)
	ans[i] += ind_r - ind_l
print(*ans, sep='\n')


import sys
input = sys.stdin.readline

def main():
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	MX = int(100000.0)
	primeFactors = [[] for _ in range(MX + 1)]
	for i in range(2, MX + 1):
		if len(primeFactors[i]) > 0:
			continue
		for j in range(i, MX + 1, i):
			primeFactors[j].append(i)
	MXH = 18
	nxt = [N for _ in range(MX + 1)]
	dp = [[N for _ in range(N + 1)] for __ in range(MXH + 1)]
	for i in range(N - 1, -1, -1):
		dp[0][i] = dp[0][i + 1]
		for factor in primeFactors[A[i]]:
			dp[0][i] = min(dp[0][i], nxt[factor])
			nxt[factor] = i
	for i in range(1, MXH + 1):
		for j in range(N):
			dp[i][j] = dp[i - 1][dp[i - 1][j]]
	for _ in range(Q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		cnt = 1
		for i in range(MXH, -1, -1):
			if dp[i][l] <= r:
				cnt += 1 << i
				l = dp[i][l]
		sys.stdout.write(f'{cnt}\n')
main()


import sys
input = sys.stdin.readline
from collections import Counter

def sieve(n):
	prime = [-1] * (n + 1)
	for i in range(2, n + 1):
		if prime[i] == -1:
			for j in range(i, n + 1, i):
				prime[j] = i
	return prime
prime = sieve(100010)
fac_loc = {}
fac = {}
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
FACT = [[] for i in range(10 ** 5 + 1)]
for i in range(2, 10 ** 5):
	if len(FACT[i]) == 0:
		for j in range(i, 10 ** 5 + 1, i):
			FACT[j].append(i)
DP = [-1] * n
j = 0
C = Counter()
for i in range(n):
	while j < n:
		for f in FACT[A[j]]:
			if C[f] >= 1:
				break
		else:
			for f in FACT[A[j]]:
				C[f] += 1
			j += 1
			continue
		break
	DP[i] = j
	for f in FACT[A[i]]:
		C[f] -= 1
reach = DP
dp = [[0 for i in range(20)] for j in range(n)]
for j in range(20):
	for i in range(n):
		if j == 0:
			dp[i][j] = reach[i]
		elif dp[i][j - 1] == n:
			dp[i][j] = n
		else:
			dp[i][j] = dp[dp[i][j - 1]][j - 1]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ans = 0
	if l == r:
		print(1)
		continue
	while l < r:
		for j in range(20):
			if dp[l][j] > r:
				if j != 0:
					ans += 2 ** (j - 1)
				l = dp[l][j - 1]
				break
			elif dp[l][j] == r:
				ans += 2 ** j
				l = r
				break
	print(ans + 1)


import sys, os, io
input = sys.stdin.readline
from collections import defaultdict

def factorize(n):
	fct = defaultdict(lambda : 0)
	b = 2
	while b * b <= n:
		while n % b == 0:
			n //= b
			fct[b] += 1
		b = b + 1
	if n > 1:
		fct[n] += 1
	return fct.keys()
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
facts = [factorize(a) for a in A]
dic1 = {i: i for i in range(N)}
left = 0
lis = defaultdict(lambda : 0)
for fact in facts[0]:
	lis[fact] += 1
for i in range(N):
	dic1[i] = left
	for j in range(left + 1, N):
		check = True
		for fact in facts[j]:
			if lis[fact] > 0:
				check = False
				break
		if not check:
			break
		dic1[i] = j
		left += 1
		for fact in facts[j]:
			lis[fact] += 1
	for fact in facts[i]:
		lis[fact] -= 1
dic2 = {i: -1 for i in range(N)}
lis2 = [[] for _ in range(N)]
for i in range(N):
	if dic2[i] == -1:
		p = i
		while p < N - 1 and dic2[p] == -1:
			lis2[i].append(p)
			dic2[p] = i
			p = dic1[p] + 1
		lis2[i].append(p)
		if p < N and dic2[p] == -1:
			dic2[p] = i
ans = [0] * Q
from bisect import *
for i in range(Q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	start = l
	while r > lis2[dic2[start]][-1]:
		ans[i] += len(lis2[dic2[start]]) - bisect_right(lis2[dic2[start]], start)
		start = lis2[dic2[start]][-1]
	ind_l = bisect_right(lis2[dic2[start]], start) - 1
	ind_r = bisect_right(lis2[dic2[start]], r)
	ans[i] += ind_r - ind_l
print(*ans, sep='\n')


import io
import os
from collections import defaultdict

def sieveSmallestPrime(n):
	smallestPrime = [-1] * n
	for i in range(2, n):
		if smallestPrime[i] == -1:
			smallestPrime[i] = i
			for j in range(i * i, n, i):
				if smallestPrime[j] == -1:
					smallestPrime[j] = i
	return smallestPrime
smallestPrime = sieveSmallestPrime(10 ** 5 + 1)

def getPrimeFactors(x):
	curr = x
	while curr > 1:
		p = smallestPrime[curr]
		count = 1
		curr //= p
		while curr % p == 0:
			curr //= p
			count += 1
		yield (p, count)

def solve(N, Q, A, queries):
	pToIndices = defaultdict(list)
	prev = [-1] * (N + 1)
	for (r, x) in enumerate(A):
		l = prev[r - 1] if r > 0 else -1
		for (p, count) in getPrimeFactors(x):
			if pToIndices[p]:
				l = max(l, pToIndices[p][-1])
			pToIndices[p].append(r)
		prev[r] = l
	prevs = [prev]
	for level in range(1, 20):
		prevs.append([-1] * (N + 1))
		for i in range(N):
			prevs[level][i] = prevs[level - 1][prevs[level - 1][i]]
	ans = []
	for (l, r) in queries:
		l -= 1
		i = r - 1
		count = 1
		for level in reversed(range(20)):
			if prevs[level][i] >= l:
				i = prevs[level][i]
				count += 1 << level
		ans.append(count)
	return '\n'.join(map(str, ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N, Q) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	queries = [[int(x) for x in input().split()] for i in range(Q)]
	ans = solve(N, Q, A, queries)
	print(ans)


MAXPRIME = 100000
primeFactors = [[] for _ in range(MAXPRIME + 1)]
for i in range(2, MAXPRIME + 1):
	if len(primeFactors[i]) == 0:
		for j in range(i, MAXPRIME + 1, i):
			primeFactors[j].append(i)

def main():
	(n, q) = readIntArr()
	arr = readIntArr()
	elemPrimes = [inf for _ in range(100001)]
	furthestCoprimeIndex = [inf for _ in range(n)]
	for i in range(n - 1, -1, -1):
		for p in primeFactors[arr[i]]:
			furthestCoprimeIndex[i] = min(furthestCoprimeIndex[i], elemPrimes[p] - 1)
			elemPrimes[p] = i
	furthest2 = furthestCoprimeIndex
	currmin = inf
	for i in range(n - 1, -1, -1):
		furthest2[i] = min(furthest2[i], currmin)
		currmin = min(currmin, furthest2[i])
	maxPower = 18
	dp = [[inf for _ in range(maxPower)] for __ in range(n)]
	for i in range(n):
		dp[i][0] = furthest2[i]
	for j in range(1, maxPower):
		for i in range(n):
			if dp[i][j - 1] + 1 >= n:
				break
			else:
				dp[i][j] = dp[dp[i][j - 1] + 1][j - 1]
	allans = []
	for _ in range(q):
		(l, r) = readIntArr()
		l -= 1
		r -= 1
		r2 = l - 1
		cnts = 0
		while True:
			l2 = r2 + 1
			breakOuter = False
			for j in range(maxPower):
				if dp[l2][j] >= r:
					if j == 0:
						cnts += 1
						breakOuter = True
					else:
						cnts += 1 << j - 1
						r2 = dp[l2][j - 1]
					break
			if breakOuter:
				break
		allans.append(cnts)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase

def main():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	inde = [[] for _ in range(10 ** 5 + 1)]
	for (ind, i) in enumerate(a):
		inde[i].append(ind)
	st = [n + 1] * n
	sieve = [0] * (10 ** 5 + 1)
	for i in range(2, 10 ** 5 + 1):
		me = []
		if not sieve[i]:
			for x in range(i, 10 ** 5 + 1, i):
				sieve[x] = 1
				me += inde[x]
		me.sort()
		for j in range(len(me) - 1):
			st[me[j]] = min(st[me[j]], me[j + 1])
	for i in range(n - 2, -1, -1):
		st[i] = min(st[i], st[i + 1])
	xx = n.bit_length()
	lifting = [[n + 1] * xx for _ in range(n)]
	for i in range(n - 2, -1, -1):
		if st[i] != n + 1:
			l = st[i]
			lifting[i][0] = l
			j = 0
			while j != xx - 1 and l != n + 1 and (lifting[l][j] != n + 1):
				lifting[i][j + 1] = lifting[l][j]
				l = lifting[l][j]
				j += 1
	powe = [pow(2, i) for i in range(xx)]
	for _ in range(q):
		(l, r) = map(lambda xxx: int(xxx) - 1, input().split())
		ans = 1
		for j in range(xx - 1, -1, -1):
			if lifting[l][j] <= r:
				ans += powe[j]
				l = lifting[l][j]
		print(ans)
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')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


import sys
input = sys.stdin.readline
MAX = 10 ** 5
pf = list(range(MAX + 1))
p = 2
while p * p <= MAX:
	if pf[p] == p:
		for m in range(p * p, MAX + 1, p):
			pf[m] = p
	p += 1

def prime_factors(n):
	while n > 1:
		p = pf[n]
		while n % p == 0:
			n //= p
		yield p
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
LOG = 17
nxt = [[-1] * (n + 1) for _ in range(LOG)]
last = {}
for i in range(n - 1, -1, -1):
	nxt[0][i] = nxt[0][i + 1] if i + 1 < n else i + 1
	for p in prime_factors(a[i]):
		if p in last:
			nxt[0][i] = min(nxt[0][i], last[p])
		last[p] = i
	for l in range(1, LOG):
		j = nxt[l - 1][i]
		nxt[l][i] = nxt[l - 1][j] if j != -1 else -1
for _ in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	res = 0
	for e in range(LOG - 1, -1, -1):
		if l <= nxt[e][l] <= r:
			l = nxt[e][l]
			res += 2 ** e
	if l < r:
		res += 1
	print(res)


from sys import stdin, stdout
import bisect
import math

def get_prime(n):
	nn = math.ceil(math.sqrt(n))
	prime = [2]
	for x in range(3, nn + 1, 2):
		is_prime = True
		for p in prime:
			if p * p > x:
				break
			if x % p == 0:
				is_prime = False
				break
		if is_prime:
			prime.append(x)
	return prime

def main():
	(n, q) = list(map(int, stdin.readline().split()))
	N = 10 ** 5 + 3
	prime = get_prime(N)
	arr = list(map(int, stdin.readline().split()))
	p_dp = [n] * N
	cut = [[n for _ in range(n + 1)] for _ in range(18)]
	cut[0][n] = n
	for i in range(n - 1, -1, -1):
		p_set = set()
		xx = arr[i]
		for p in prime:
			if p * p > xx:
				break
			while xx % p == 0:
				xx = xx // p
				p_set.add(p)
		if xx > 1:
			p_set.add(xx)
		cut[0][i] = cut[0][i + 1]
		for y in p_set:
			cut[0][i] = min(cut[0][i], p_dp[y])
			p_dp[y] = i
	for i in range(1, 18):
		for j in range(n):
			cut[i][j] = cut[i - 1][cut[i - 1][j]]
	for _ in range(q):
		(l, r) = list(map(int, stdin.readline().split()))
		l -= 1
		r -= 1
		cost = 1
		for i in range(17, -1, -1):
			if cut[i][l] <= r:
				cost += 2 ** i
				l = cut[i][l]
		stdout.write(str(cost) + '\n')
main()


import sys
input = sys.stdin.readline
from collections import Counter

def sieve(n):
	prime = [-1] * (n + 1)
	for i in range(2, n + 1):
		if prime[i] == -1:
			for j in range(i, n + 1, i):
				prime[j] = i
	return prime
prime = sieve(100010)
fac_loc = {}
fac = {}
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
reach = [n] * n
for i in range(n - 1, -1, -1):
	if a[i] not in fac:
		p = []
		num = a[i]
		while num != 1:
			f = prime[num]
			p.append(f)
			while num % f == 0:
				num = num // f
		fac[a[i]] = p
	p = fac[a[i]]
	minn = 10 ** 18
	for j in p:
		if j in fac_loc:
			minn = min(minn, fac_loc[j])
		fac_loc[j] = i
	if minn != 10 ** 18:
		reach[i] = minn
	if i != n - 1:
		reach[i] = min(reach[i + 1], reach[i])
dp = [[0 for i in range(20)] for j in range(n)]
for j in range(20):
	for i in range(n):
		if j == 0:
			dp[i][j] = reach[i]
		elif dp[i][j - 1] == n:
			dp[i][j] = n
		else:
			dp[i][j] = dp[dp[i][j - 1]][j - 1]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ans = 0
	if l == r:
		print(1)
		continue
	while l < r:
		for j in range(20):
			if dp[l][j] > r:
				if j != 0:
					ans += 2 ** (j - 1)
				l = dp[l][j - 1]
				break
			elif dp[l][j] == r:
				ans += 2 ** j
				l = r
				break
	print(ans + 1)


import sys
input = sys.stdin.buffer.readline
spf = [0] * (10 ** 5 + 1)
primes = []
for i in range(2, 10 ** 5 + 1):
	if spf[i] == 0:
		spf[i] = i
		primes.append(i)
	j = 0
	while j < len(primes) and primes[j] <= spf[i] and (primes[j] * i <= 10 ** 5):
		spf[primes[j] * i] = primes[j]
		j += 1
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
ancestor = [[n] * 20 for i in range(10 ** 5 + 1)]
next_start = n
last_occurence = [n] * (10 ** 5 + 1)
for i in range(n - 1, -1, -1):
	lst = -1
	while a[i] != 1:
		if lst != spf[a[i]]:
			next_start = min(next_start, last_occurence[spf[a[i]]])
			last_occurence[spf[a[i]]] = i
		lst = spf[a[i]]
		a[i] //= spf[a[i]]
	ancestor[i][0] = next_start
	for j in range(1, 20):
		ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	subarrays = 1
	for j in range(19, -1, -1):
		if ancestor[l][j] <= r:
			l = ancestor[l][j]
			subarrays += 1 << j
	print(subarrays)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
maxn = 100002
primes = []
spf = [0] * (maxn + 1)
for i in range(2, maxn):
	if spf[i] == 0:
		spf[i] = i
		primes.append(i)
	j = 0
	while j < len(primes) and primes[j] <= spf[i] and (primes[j] * i <= maxn):
		spf[primes[j] * i] = primes[j]
		j += 1

def fun(n):
	ans = []
	while n > 1:
		x = spf[n]
		if len(ans) == 0 or ans[-1] != x:
			ans.append(x)
		n //= x
	return ans

def solve():
	(n, q) = li()
	a = li()
	last = [n for i in range(100001)]
	nxt = [n for i in range(n + 1)]
	dp = [[0 for i in range(21)] for j in range(100001)]
	for i in range(20):
		dp[n][i] = n + 1
	for i in range(n - 1, -1, -1):
		x = a[i]
		nxt[i] = nxt[i + 1]
		while x > 1:
			k = spf[x]
			while x % k == 0:
				x //= k
			nxt[i] = min(nxt[i], last[k])
			last[k] = i
		dp[i][0] = nxt[i]
		for j in range(1, 20):
			if dp[i][j - 1] == n + 1:
				dp[i][j] = n + 1
				continue
			dp[i][j] = dp[dp[i][j - 1]][j - 1]
	for _ in range(q):
		(l, r) = li()
		l -= 1
		r -= 1
		ans = 0
		for i in range(19, -1, -1):
			if dp[l][i] <= r:
				l = dp[l][i]
				ans += 2 ** i
		if l <= r:
			ans += 1
		print(ans)
t = 1
for _ in range(t):
	solve()


from sys import stdin, stdout
from typing import Iterable
input = lambda : stdin.readline()[:-1]

def rn() -> int:
	return int(input())

def rns() -> Iterable[int]:
	return map(int, input().split())

def write(line: str):
	stdout.write(line + '\n')

def writen(x: int):
	write(str(x))

def eratosfen(limit):
	simple = [True for _ in range(limit)]
	simple[0] = False
	simple[1] = False
	res = []
	for x in range(limit):
		if not simple[x]:
			continue
		res.append(x)
		r = x * 2
		while r < limit:
			simple[r] = False
			r += x
	return (res, simple)

def decompose(x, simples, is_simple):
	for simple in simples:
		if simple ** 2 > x:
			break
		if x % simple == 0:
			yield simple
			while x % simple == 0:
				x //= simple
	if is_simple[x]:
		yield x

def main():
	(simples, is_simple) = eratosfen(10 ** 5 + 1)
	(n, q) = rns()
	d = {}
	h0 = [0]
	last_l = 0
	for (i, x) in enumerate(rns(), 1):
		for divider in decompose(x, simples, is_simple):
			if divider in d:
				last_l = max(last_l, d[divider])
			d[divider] = i
		h0.append(last_l)
	h = [h0]
	log2_100000 = 17
	for i in range(1, log2_100000 + 1):
		hi = [0 for _ in range(len(h0))]
		for j in range(len(hi) - 1, -1, -1):
			prev = h[-1][j]
			pre_prev = h[-1][prev]
			hi[j] = pre_prev
		h.append(hi)
	for _ in range(q):
		(l, r) = rns()
		res = 0
		c = r
		while c >= l:
			next_hop = 0
			i = log2_100000
			while i >= 0:
				next_hop = h[i][c]
				if next_hop >= l:
					break
				i -= 1
			res += 2 ** max(0, i)
			c = next_hop
		print(res)
main()


from sys import stdin, stdout

def cut(n, a_a):
	N = max(a_a)
	p_a = seive_a(N)
	dic = {}
	b_a = [[-1 for j in range(20)] for i in range(n)]
	b_a[n - 1][0] = n
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			r = n
		else:
			r = b_a[i + 1][0]
		for p in p_a[a_a[i]]:
			if p in dic:
				r = min(r, dic[p])
			dic[p] = i
		b_a[i][0] = r
	for i in range(1, 20):
		for j in range(n):
			if b_a[j][i - 1] == -1 or b_a[j][i - 1] == n or b_a[b_a[j][i - 1]][i - 1] == -1:
				continue
			b_a[j][i] = b_a[b_a[j][i - 1]][i - 1]
	return b_a

def solve(b_a, l, r):
	res = 0
	for step in range(19, -1, -1):
		if b_a[l][step] != -1 and b_a[l][step] <= r:
			res += 1 << step
			l = b_a[l][step]
	return res + 1

def seive_a(n):
	p_a = [[] for i in range(n + 1)]
	for i in range(2, n + 1):
		if len(p_a[i]) > 0:
			continue
		j = i
		while j <= n:
			p_a[j].append(i)
			j += i
	return p_a
(n, q) = map(int, stdin.readline().split())
a_a = list(map(int, stdin.readline().split()))
b_a = cut(n, a_a)
for _ in range(q):
	(l, r) = map(int, stdin.readline().split())
	res = solve(b_a, l - 1, r - 1)
	stdout.write(str(res) + '\n')


def primeFactor(N):
	(i, n) = (2, N)
	ret = {}
	(d, sq) = (2, 99)
	while i <= sq:
		k = 0
		while n % i == 0:
			(n, k, ret[i]) = (n // i, k + 1, k + 1)
		if k > 0 or i == 97:
			sq = int(n ** (1 / 2) + 0.5)
		if i < 4:
			i = i * 2 - 1
		else:
			(i, d) = (i + d, d ^ 6)
	if n > 1:
		ret[n] = 1
	return ret

def divisor(n):
	div = [1]
	for (i, j) in primeFactor(n).items():
		div = [i ** k * d for d in div for k in range(j + 1)]
	return div

def PrimeNumSet(N):
	M = int(N ** 0.5)
	seachList = [i for i in range(2, N + 1)]
	primes = []
	while seachList:
		if seachList[0] > M:
			break
		primes.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	return primes + seachList

def LCM(b, mo=10 ** 9 + 7):
	prs = PrimeNumSet(max(b))
	M = dict(zip(prs, [0] * len(prs)))
	for i in b:
		dc = primeFactor(i)
		for (j, k) in dc.items():
			M[j] = max(M[j], k)
	r = 1
	for (j, k) in M.items():
		if k != 0:
			r *= pow(j, k, mo)
			r %= mo
	return r

def extgcd(x, y):
	if y == 0:
		return (1, 0)
	(r0, r1, s0, s1) = (x, y, 1, 0)
	while r1 != 0:
		(r0, r1, s0, s1) = (r1, r0 % r1, s1, s0 - r0 // r1 * s1)
	return (s0, (r0 - s0 * x) // y, x * s0 + y * (r0 - s0 * x) // y)

def crt(rems, mods):
	n = len(rems)
	if n != len(mods):
		return NotImplemented
	(x, d) = (0, 1)
	for (r, m) in zip(rems, mods):
		(a, b, g) = extgcd(d, m)
		(x, d) = ((m * b * x + d * a * r) // g, d * (m // g))
		x %= d
	for (r, m) in zip(rems, mods):
		if r != x % m:
			return (-1, d)
	return (x, d)

def intsqrt(x):
	if x < 0:
		return NotImplemented
	rt = int(x ** 0.5) - 1
	while (rt + 1) ** 2 <= x:
		rt += 1
	return rt
show_flg = False
show_flg = True
ans = 0
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
from collections import deque, defaultdict, Counter

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]
(n, q) = LI()
a = LI()
pf = dict()
d = dict()
for i in set(a):
	pf[i] = primeFactor(i).items()
(l, r) = (0, 0)
div = defaultdict(int)
a += (a[-1],)
nx = [n] * (n + 1)
while r <= n:
	if all([div[p] == 0 for (p, cnt) in pf[a[r]]]):
		for (p, cnt) in pf[a[r]]:
			div[p] += cnt
		r += 1
	else:
		nx[l] = r
		if l < r:
			for (p, cnt) in pf[a[l]]:
				div[p] -= cnt
			l += 1
		else:
			for (p, cnt) in pf[a[r]]:
				div[p] += cnt
			r += 1
nx = [nx]
m = n.bit_length()
for k in range(m):
	nnx = [0] * (n + 1)
	for i in range(n + 1):
		nnx[i] = nx[k][nx[k][i]]
	nx.append(nnx)
for i in range(q):
	(l, r) = LI_()
	t = 1
	for p in range(m, -1, -1):
		if nx[p][l] <= r:
			t += 1 << p
			l = nx[p][l]
	print(t)


import os
import sys
import time
from io import BytesIO, IOBase

def main():
	limit = 10 ** 5 + 1
	R = [[] for _ in range(limit)]
	(n, q) = li_input()
	a = li_input()
	simples = {1: n}
	for i in range(2, limit):
		if not R[i]:
			simples[i] = n
			for j in range(i, limit, i):
				R[j].append(i)
	A = [[n] * (n + 1)]
	for i in range(n - 1, -1, -1):
		A[0][i] = A[0][i + 1]
		for div in R[a[i]]:
			if div in simples:
				A[0][i] = min(A[0][i], simples[div])
				simples[div] = i
	need_to_continue = True
	while need_to_continue:
		need_to_continue = False
		A.append([n] * (n + 1))
		for i in range(n):
			if A[-2][i] != n:
				A[-1][i] = A[-2][A[-2][i]]
				if A[-1][i] != n:
					need_to_continue = True
	out = []
	for qq in range(q):
		ans = 1
		(l, r) = li_input()
		l -= 1
		r -= 1
		for i in range(len(A) - 1, -1, -1):
			if A[i][l] <= r:
				ans += 1 << i
				l = A[i][l]
		out.append(ans)
	print('\n'.join(map(str, out)))
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def i_input():
	return int(input())

def l_input():
	return input().split()

def li_input():
	return list(map(int, l_input()))

def il_input():
	return list(map(int, l_input()))
TT = time.time()
main()


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right
prime_size = 10 ** 5 + 10
primes = []
sfc = [i for i in range(prime_size)]
for i in range(2, prime_size):
	if sfc[i] == i:
		primes.append(i)
	pt = 0
	while pt < len(primes) and primes[pt] * i < prime_size and (primes[pt] <= i):
		sfc[primes[pt] * i] = primes[pt]
		pt += 1

def main(case):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = [[n] * n for _ in range(17)]
	last = [n] * prime_size
	for i in range(n - 1, -1, -1):
		mn = n
		if i < n - 1:
			mn = min(mn, dp[0][i + 1])
		fc = arr[i]
		while fc >= 2:
			mn = min(mn, last[sfc[fc]])
			last[sfc[fc]] = i
			div = sfc[fc]
			while fc % div == 0:
				fc //= div
		dp[0][i] = mn
	for i in range(1, 17):
		for j in range(n):
			if dp[i - 1][j] == n:
				dp[i][j] = n
			else:
				dp[i][j] = dp[i - 1][dp[i - 1][j]]
	for _ in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		ans = 1
		for i in range(16, -1, -1):
			if a < b and dp[i][a] <= b:
				ans += 2 ** i
				a = dp[i][a]
		print(ans)
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')
for _ in range(1):
	main(_ + 1)


import sys
input = sys.stdin.readline
from collections import Counter
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
FACT = [[] for i in range(10 ** 5 + 1)]
for i in range(2, 10 ** 5):
	if len(FACT[i]) == 0:
		for j in range(i, 10 ** 5 + 1, i):
			FACT[j].append(i)
DP = [-1] * n
j = 0
C = Counter()
for i in range(n):
	while j < n:
		for f in FACT[A[j]]:
			if C[f] >= 1:
				break
		else:
			for f in FACT[A[j]]:
				C[f] += 1
			j += 1
			continue
		break
	DP[i] = j
	for f in FACT[A[i]]:
		C[f] -= 1
DPD = [DP]
for i in range(20):
	NDP = [n] * n
	for j in range(n):
		if DPD[-1][j] < n:
			NDP[j] = DPD[-1][DPD[-1][j]]
		else:
			break
	DPD.append(NDP)
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	ANS = 0
	while l < r:
		for j in range(20):
			if DPD[j][l] > r:
				if j > 0:
					ANS += 2 ** (j - 1)
				l = DPD[j - 1][l]
				break
			elif DPD[j][l] == r:
				ANS += 2 ** j
				l = r
				break
	print(ANS + 1)


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')

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

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

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
flag = Prime(10 ** 5)
t = 1
for i in range(t):
	(n, q) = RL()
	a = RLL()
	r = AI(n, n - 1)
	g = G(10 ** 5)
	x = a[-1]
	while flag[x]:
		c = flag[x]
		while x % c == 0:
			x //= c
		g[c].append(n - 1)
	if x > 1:
		g[x].append(n - 1)
	for i in range(n - 2, -1, -1):
		x = a[i]
		while flag[x]:
			c = flag[x]
			while x % c == 0:
				x //= c
			if g[c]:
				r[i] = min(r[i], g[c][-1] - 1)
			g[c].append(i)
		if x > 1:
			if g[x]:
				r[i] = min(r[i], g[x][-1] - 1)
			g[x].append(i)
		r[i] = min(r[i], r[i + 1])
	dp = [[n] * 18 for i in range(n + 1)]
	for i in range(n):
		dp[i][0] = r[i] + 1
	for j in range(1, 18):
		for i in range(n):
			dp[i][j] = dp[dp[i][j - 1]][j - 1]
	for i in range(q):
		(a, b) = RL()
		a -= 1
		b -= 1
		c = 0
		for i in range(17, -1, -1):
			if dp[a][i] > b:
				continue
			a = dp[a][i]
			c += 1 << i
		if a <= b:
			c += 1
		print(c)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict

def sieve(n):
	fact = [float('inf')] * (n + 1)
	fact[1] = 1
	for i in range(2, n + 1):
		if fact[i] == float('inf'):
			j = i
			while j <= n:
				fact[j] = min(fact[j], i)
				j += i
	return fact

def osa_k(n):
	fct = defaultdict(lambda : 0)
	while n > 1:
		fct[facts[n]] += 1
		n //= facts[n]
	return fct.keys()
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
facts = sieve(max(A))
facts = [osa_k(a) for a in A]
dic1 = {i: i for i in range(N)}
left = 0
lis = defaultdict(lambda : 0)
for fact in facts[0]:
	lis[fact] += 1
for i in range(N):
	dic1[i] = left
	for j in range(left + 1, N):
		check = True
		for fact in facts[j]:
			if lis[fact] > 0:
				check = False
				break
		if not check:
			break
		dic1[i] = j
		left += 1
		for fact in facts[j]:
			lis[fact] += 1
	for fact in facts[i]:
		lis[fact] -= 1
dic2 = {i: -1 for i in range(N)}
lis2 = [[] for _ in range(N)]
for i in range(N):
	if dic2[i] == -1:
		p = i
		while p < N - 1 and dic2[p] == -1:
			lis2[i].append(p)
			dic2[p] = i
			p = dic1[p] + 1
		lis2[i].append(p)
		if p < N and dic2[p] == -1:
			dic2[p] = i
ans = [0] * Q
from bisect import *
for i in range(Q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	start = l
	while r > lis2[dic2[start]][-1]:
		ans[i] += len(lis2[dic2[start]]) - bisect_right(lis2[dic2[start]], start)
		start = lis2[dic2[start]][-1]
	ind_l = bisect_right(lis2[dic2[start]], start) - 1
	ind_r = bisect_right(lis2[dic2[start]], r)
	ans[i] += ind_r - ind_l
print(*ans, sep='\n')


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
(n, q) = MI()
A = LI()
prime_fac = [[] for _ in range(10 ** 5 + 1)]
nex = [0] * (10 ** 5 + 1)
for i in range(2, 10 ** 5 + 1):
	if not prime_fac[i]:
		nex[i] = n
		for j in range(i, 10 ** 5 + 1, i):
			prime_fac[j].append(i)
dp = [[0] * 18 for _ in range(n + 1)]
dp[n][0] = n
for i in range(n - 1, -1, -1):
	a = A[i]
	dp[i][0] = dp[i + 1][0]
	for p in prime_fac[a]:
		dp[i][0] = min(dp[i][0], nex[p])
		nex[p] = i
for j in range(1, 18):
	for i in range(n + 1):
		dp[i][j] = dp[dp[i][j - 1]][j - 1]
for _ in range(q):
	(l, r) = MI()
	l -= 1
	r -= 1
	ans = 1
	for j in range(17, -1, -1):
		if dp[l][j] <= r:
			ans += 1 << j
			l = dp[l][j]
	print(ans)


import sys, os, io
from collections import defaultdict
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
maxn = 100002
primes = []
spf = [0] * (maxn + 1)
for i in range(2, maxn):
	if spf[i] == 0:
		spf[i] = i
		primes.append(i)
	j = 0
	while j < len(primes) and primes[j] <= spf[i] and (primes[j] * i <= maxn):
		spf[primes[j] * i] = primes[j]
		j += 1

def fun(n):
	ans = []
	while n > 1:
		x = spf[n]
		if len(ans) == 0 or ans[-1] != x:
			ans.append(x)
		n //= x
	return ans
(n, q) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
graph = [[] for i in range(10 ** 5 + 2)]
for i in range(n):
	p = fun(a[i])
	for j in p:
		graph[j].append(i)
nxt = [10 ** 6] * n
for i in range(n):
	p = fun(a[i])
	for j in p:
		nind = bisect.bisect_right(graph[j], i)
		if nind != len(graph[j]):
			nxt[i] = min(nxt[i], graph[j][nind])
for i in range(n - 2, -1, -1):
	nxt[i] = min(nxt[i], nxt[i + 1])
cnt = [0] * n
l = 0
while l < n:
	l = nxt[l]
	if l >= n:
		break
	cnt[l] += 1
for i in range(1, n):
	cnt[i] += cnt[i - 1]
for i in range(q):
	(l, r) = [int(i) - 1 for i in input().split()]
	if l == 0 or cnt[l] != cnt[l - 1]:
		print(cnt[r] - cnt[l] + 1)
	else:
		ans = 0
		while l <= r:
			ans += 1
			l = nxt[l]
			if l >= len(cnt):
				break
			if cnt[l] != cnt[l - 1]:
				break
		if l > r:
			print(ans)
		else:
			print(ans + cnt[r] - cnt[l] + 1)


import sys
input = sys.stdin.buffer.readline

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]
(n, q) = LI()
arr = LI()
prime_last_appear_at = dict()
dp = [[n] * (n + 1) for i in range(18)]
have_primes = [[] for _ in range(10 ** 5 + 3)]
for p in range(2, 10 ** 5 + 2):
	if not have_primes[p]:
		prime_last_appear_at[p] = n
		i = p
		while i < len(have_primes):
			have_primes[i].append(p)
			i += p
for i in range(n - 1, -1, -1):
	dp[0][i] = dp[0][i + 1]
	for p in have_primes[arr[i]]:
		dp[0][i] = min(dp[0][i], prime_last_appear_at[p])
		prime_last_appear_at[p] = i
for i in range(1, len(dp)):
	for j in range(n):
		dp[i][j] = dp[i - 1][dp[i - 1][j]]
for _ in range(q):
	(l, r) = LI_()
	cur = l
	res = 1
	for jump in range(len(dp) - 1, -1, -1):
		if dp[jump][cur] <= r:
			res += 1 << jump
			cur = dp[jump][cur]
	print(res)


import os
import sys
import time
from functools import lru_cache
from io import BytesIO, IOBase

def main():
	limit = 10 ** 5 + 1
	R = [0] * limit
	for i in range(2, limit):
		if not R[i]:
			for j in range(i * i, limit, i):
				if not R[j]:
					R[j] = i

	@lru_cache(None)
	def get_divs(n):
		if n == 1:
			return tuple()
		s = set()
		while R[n]:
			s.add(R[n])
			n //= R[n]
		s.add(n)
		return s
	(n, q) = li_input()
	a = li_input()
	all_divs = {}
	p = [0] * n
	j = 0
	for (i, aa) in enumerate(a):
		while j < n:
			divs_j = get_divs(a[j])
			if any((div_j in all_divs for div_j in divs_j)):
				break
			for div_j in divs_j:
				if div_j in all_divs:
					all_divs[div_j] += 1
				else:
					all_divs[div_j] = 1
			j += 1
		p[i] = j
		divs_i = get_divs(a[i])
		for div_i in divs_i:
			all_divs[div_i] -= 1
			if not all_divs[div_i]:
				all_divs.pop(div_i)
	A = [p]
	need_to_continue = True
	while need_to_continue:
		need_to_continue = False
		A.append([n] * n)
		for i in range(n):
			if A[-2][i] != n:
				A[-1][i] = A[-2][A[-2][i]]
				if A[-1][i] != n:
					need_to_continue = True
	out = []
	for qq in range(q):
		ans = 1
		(l, r) = li_input()
		l -= 1
		r -= 1
		for i in range(len(A) - 1, -1, -1):
			if A[i][l] <= r:
				ans += 1 << i
				l = A[i][l]
		out.append(ans)
	print('\n'.join(map(str, out)))
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def i_input():
	return int(input())

def l_input():
	return input().split()

def li_input():
	return list(map(int, l_input()))

def il_input():
	return list(map(int, l_input()))
TT = time.time()
main()


import sys
import bisect
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
prime = [[] for i in range(10 ** 5 + 3)]

def gen_prime():
	n = 10 ** 5 + 1
	for i in range(2, n + 1, 2):
		prime[i].append(2)
	for i in range(3, n + 1, 2):
		if prime[i] == []:
			for j in range(i, n + 1, i):
				prime[j].append(i)
gen_prime()

def dfs(root, par):
	global gp, cost, dp
	dp[root] = cost[root]
	for i in gp[root]:
		if i == par:
			continue
		dfs(i, root)
		dp[root] = max(dp[root], dp[i])

def hnbhai():
	(n, q) = sd()
	last = [n + 1 for _ in range(10 ** 5 + 2)]
	a = [0] + sd()
	kthpar = [[0 for i in range(18)] for j in range(n + 2)]
	kthpar[n + 1][0] = n + 1
	for i in range(n, 0, -1):
		kthpar[i][0] = kthpar[i + 1][0]
		for child in prime[a[i]]:
			kthpar[i][0] = min(kthpar[i][0], last[child])
			last[child] = i
	for i in range(n + 1, 0, -1):
		for j in range(1, 18):
			kthpar[i][j] = kthpar[kthpar[i][j - 1]][j - 1]
	for t in range(q):
		(l, r) = sd()
		ans = 1
		for i in range(17, -1, -1):
			if kthpar[l][i] <= r:
				ans += 1 << i
				l = kthpar[l][i]
		print(ans)
for _ in range(1):
	hnbhai()