Read problems statements in Mandarin Chinese  and Russian. 

You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the gcd(Greatest Common Divisor) of the array after excluding the part from range L to R inclusive (1 Based indexing). You are guaranteed that after excluding the part of the array 
remaining array is non empty.
 
------ Input ------ 

First line of input contains an integer T denoting number of test cases.  
For each test case, first line will contain two space separated integers N, Q.  
Next line contains N space separated integers denoting array A. 
For next Q lines, each line will contain a query denoted by two space separated integers L, R. 

------ Output ------ 

For each query, print a single integer representing the answer of that query.

------ Constraints ------ 

Subtask #1: 40 points
$2 ≤ T, N ≤ 100, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 10^{5}$
	$1 ≤ L, R ≤ N and L ≤ R$

Subtask #2: 60 points
$2 ≤ T, N ≤ 10^{5}, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 10^{5}$
	$1 ≤ L, R ≤ N and L ≤ R$
	$ Sum of N over all the test cases will be less than or equal to 10^{6}.Warning :  Large IO(input output), please use faster method for IO. 

----- Sample Input 1 ------ 
1
3 3
2 6 9
1 1
2 2
2 3
----- Sample Output 1 ------ 
3
1
2
----- explanation 1 ------ 
Test case $1$: The given array is $[2, 6, 9]$.
- Query $1$: On excluding the range $[1,1]$, the remaining elements are $[6, 9]$. The *gcd* of $6$ and $9$ is $3$.
- Query $2$: On excluding the range $[2,2]$, the remaining elements are $[2, 9]$. The *gcd* of $2$ and $9$ is $1$.
- Query $3$: On excluding the range $[2,3]$, the remaining elements are $[2]$. The *gcd* of $2$ is $2$.

Difficulty: MEDIUM_HARD
Tags: Number theory

Preprocessing

Starter code:

Solutions:
from math import gcd
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = [0]
	suf = [0]
	for i in range(n):
		pre.append(gcd(pre[-1], a[i]))
	for i in range(n - 1, -1, -1):
		suf.append(gcd(suf[-1], a[i]))
	suf.reverse()
	for i in range(q):
		(l, h) = map(int, input().split())
		print(gcd(pre[l - 1], suf[h]))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = []
	(l, r) = ([0] * (n + 2), [0] * (n + 2))
	a.append(0)
	a = a + list(map(int, input().split()))
	for i in range(1, n + 1):
		l[i] = gcd(l[i - 1], a[i])
	for i in range(n, 0, -1):
		r[i] = gcd(r[i + 1], a[i])
	for i in range(q):
		(l1, r1) = map(int, input().split())
		print(gcd(l[l1 - 1], r[r1 + 1]))


import math
t = int(input())
while t:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	farr = [0]
	barr = [0]
	for i in range(n):
		fgc = math.gcd(farr[-1], arr[i])
		farr.append(fgc)
		bgc = math.gcd(barr[-1], arr[-i - 1])
		barr.append(bgc)
	for _ in range(q):
		(l, r) = map(int, input().split())
		x = math.gcd(farr[l - 1], barr[-1 - r])
		print(x)
	t -= 1


def gcd(a, b):
	while b != 0:
		c = a
		a = b
		b = c % a
	return a
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	arr = [int(ele) for ele in input().split()]
	pre = [0] * (n + 1)
	suff = [0] * (n + 1)
	pre[0] = 0
	for i in range(1, n + 1):
		pre[i] = gcd(pre[i - 1], arr[i - 1])
	suff[-1] = 0
	for i in range(n - 1, -1, -1):
		suff[i] = gcd(suff[i + 1], arr[i])
	for i in range(q):
		(l, r) = map(int, input().split())
		print(gcd(pre[l - 1], suff[r]))


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
T = int(input())
for i in range(T):
	(n, q) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	pre = [0] * (n + 1)
	suf = [0] * (n + 1)
	for a in range(1, n + 1):
		pre[a] = gcd(arr[a - 1], pre[a - 1])
	for a in range(n - 1, -1, -1):
		suf[a] = gcd(arr[a], suf[a + 1])
	for z in range(q):
		(l, r) = [int(x) for x in input().split()]
		print(gcd(pre[l - 1], suf[r]))


def gcd(a, b):
	if b == 0:
		return abs(a)
	return gcd(b, a % b)
for i in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	forward = [0] * (n + 5)
	backward = [0] * (n + 5)
	for x in range(1, n + 1):
		forward[x] = gcd(forward[x - 1], a[x - 1])
	for x in range(n, 1, -1):
		backward[x] = gcd(backward[x + 1], a[x - 1])
	while q:
		(l, r) = map(int, input().split())
		print(gcd(forward[l - 1], backward[r + 1]))
		q -= 1


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	(l1, l2) = ([], [])
	g = l[0]
	for i in l:
		g = math.gcd(i, g)
		l1.append(g)
	g = l[n - 1]
	for i in l[::-1]:
		g = math.gcd(i, g)
		l2.append(g)
	l2 = l2[::-1]
	for i in range(m):
		(c1, c2) = map(int, input().split())
		if c1 - 2 >= 0 and c2 <= n - 1:
			print(math.gcd(l1[c1 - 2], l2[c2]))
		elif c1 - 2 >= 0:
			print(l1[c1 - 2])
		else:
			print(l2[c2])


def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
for _ in range(int(input())):
	(array_size, queries) = map(int, input().split())
	array = list((int(num) for num in input().strip().split()))[:array_size]
	forward_gcd = [None] * (array_size + 10)
	backward_gcd = [None] * (array_size + 10)
	forward_gcd[0] = 0
	backward_gcd[array_size] = 0
	for i in range(array_size):
		forward_gcd[i + 1] = computeGCD(forward_gcd[i], array[i])
	for k in reversed(range(len(array))):
		backward_gcd[k] = computeGCD(backward_gcd[k + 1], array[k])
	while queries > 0:
		(l, r) = map(int, input().split())
		gcd = forward_gcd[l - 1]
		gcd1 = backward_gcd[r]
		print(computeGCD(gcd, gcd1))
		queries -= 1


def gcd_iterative(a, b):
	while b != 0:
		temp = a % b
		a = b
		b = temp
	else:
		return a

def precompute_gcd_first(new_list):
	d = new_list[0]
	temp = [d]
	for (i, a) in enumerate(new_list[1:]):
		d = gcd_iterative(a, d)
		temp.append(d)
	return temp
for _ in range(int(input())):
	(N, Q) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	gcd_list_first = precompute_gcd_first(array)
	gcd_list_last = precompute_gcd_first(array[::-1])[::-1]
	for q in range(Q):
		(L, R) = list(map(int, input().split()))
		if L - 2 < 0:
			d1 = 0
		else:
			d1 = gcd_list_first[L - 2]
		if R == len(gcd_list_first):
			d2 = 0
		else:
			d2 = gcd_list_last[R]
		print(gcd_iterative(d1, d2))


from math import gcd

def solve():
	(n, q) = map(int, input().split())
	t = list(map(int, input().split()))
	prefix = [0] * (n + 2)
	suffix = [0] * (n + 2)
	prefix[0] = 0
	suffix[n + 1] = 0
	for i in range(0, n):
		prefix[i + 1] = gcd(t[i], prefix[i])
	for i in range(n - 1, -1, -1):
		suffix[i] = gcd(t[i], suffix[i + 1])
	while q:
		(l, r) = map(int, input().split())
		print(gcd(prefix[l - 1], suffix[r]))
		q -= 1

def main():
	tc = int(input())
	while tc:
		solve()
		tc -= 1
main()


import sys

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = [None] * n
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = gcd(pre[i - 1], a[i])
	suff = [None] * n
	suff[n - 1] = a[-1]
	for i in range(n - 2, -1, -1):
		suff[i] = gcd(suff[i + 1], a[i])
	for __ in range(q):
		(l, r) = map(int, input().split())
		(l, r) = (l - 1, r - 1)
		a = pre[l - 1] if l >= 1 else 0
		b = suff[r + 1] if r + 1 < n else 0
		ans = gcd(a, b)
		sys.stdout.write(str(ans) + '\n')


from math import gcd
t = int(input())
while t:
	(a, b) = list(map(int, input().split()))
	arr = []
	arr.append(0)
	arr.extend(list(map(int, input().split())))
	pregcd = [0] * (a + 2)
	sufgcd = [0] * (a + 2)
	pregcd[0] = 0
	sufgcd[a] = 0
	for i in range(1, a + 1):
		pregcd[i] = gcd(pregcd[i - 1], arr[i])
	for i in range(a, 0, -1):
		sufgcd[i] = gcd(sufgcd[i + 1], arr[i])
	while b > 0:
		(l, r) = list(map(int, input().split()))
		print(gcd(pregcd[l - 1], sufgcd[r + 1]))
		b -= 1
	t -= 1


import math
t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	forward = [0] * (n + 1)
	backward = [0] * (n + 2)
	backward[n] = arr[n]
	backward[n + 1] = 0
	for i in range(1, n + 1):
		forward[i] = math.gcd(forward[i - 1], arr[i])
	for i in range(n - 1, 0, -1):
		backward[i] = math.gcd(backward[i + 1], arr[i])
	while q > 0:
		(l, r) = map(int, input().split())
		gc = math.gcd(forward[l - 1], backward[r + 1])
		print(gc)
		q -= 1
	t -= 1


import string
from functools import lru_cache
import atexit, io
import sys
from math import log2
import math
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right, insort
from math import gcd
from math import sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
import heapq

class FenwickTree:

	def __init__(self, n):
		self.farr = [0] * (n + 1)

	def prefixSum(self, idx):
		s = 0
		while idx > 0:
			s += self.farr[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, val):
		while idx < len(self.farr):
			self.farr[idx] += val
			idx += idx & -idx

	def find(self, k):
		curr = 0
		ans = 0
		prevSum = 0
		for i in range(log2(n), -1, -1):
			if self.farr[curr + (i << i)] + prevSum < k:
				curr += 1 << i
				prevSum += self.farr[curr]
		return curr + 1

class Trie(object):

	def __init__(self):
		self.trie = {}

	def insert(self, word):
		t = self.trie
		for c in word:
			if c not in t:
				t[c] = {}
			t = t[c]
		t['-'] = True

	def search(self, word):
		t = self.trie
		for c in word:
			if c not in t:
				return False
			t = t[c]
		return '-' in t

	def startsWith(self, prefix):
		t = self.trie
		for c in prefix:
			if c not in t:
				return False
			t = t[c]
		return True

	def query(self, word):
		ans = 0
		t = self.trie
		for i in word:
			if i not in t:
				break
			ans += 1
			t = t[i]
		return ans

class FenvTree:

	def __init__(self, arr):
		arr.insert(0, 0)
		self.farr = [0]
		prefix = [0]
		for i in arr[1:]:
			prefix.append(prefix[-1] + i)
		for i in range(1, len(arr)):
			idash = i - (i & -i)
			self.farr.append(prefix[i] - prefix[idash])

	def query(self, l, r):
		return self.prefixSum(r) - self.prefixSum(l - 1)

	def prefixSum(self, idx):
		s = 0
		while idx > 0:
			s += self.farr[idx]
			idx -= idx & -idx
		return s

	def update(self, idx, val):
		while idx < len(self.farr):
			self.farr[idx] += val
			idx += idx & -idx

class DSU:

	def __init__(self, n):
		self.parent = []
		self.size = []
		for i in range(n + 1):
			self.parent.append(i)
			self.size.append(1)

	def union(self, u, v):
		pu = self.findPar(u)
		pv = self.findPar(v)
		if pu == pv:
			return
		if self.size[pu] < self.size[pv]:
			self.parent[pu] = pv
			self.size[pv] += self.size[pu]
		else:
			self.parent[pv] = pu
			self.size[pu] += self.size[pv]

	def unionByRank(self, u, v):
		pu = self.findPar(u)
		pv = self.findPar(v)
		if pu == pv:
			return
		if self.rank[pu] < self.rank[pv]:
			self.parent[pu] = pv
		elif self.rank[pv] < self.rank[pu]:
			self.parent[pv] = pu
		else:
			self.parent[pu] = pv
			self.rank[pv] += 1

	def findPar(self, node):
		if self.parent[node] == node:
			return node
		self.parent[node] = self.findPar(self.parent[node])
		return self.parent[node]

class info:

	def __init__(self, _open=0, _close=0, _full=0):
		self.open = _open
		self.close = _close
		self.full = _full

class SGTree:

	def __init__(self, n):
		self.seg = [0 for _ in range(4 * n)]

	def build(self, ind, low, high, arr):
		if low == high:
			self.seg[ind] = arr[low]
			return
		mid = (low + high) // 2
		self.build(2 * ind + 1, low, mid, arr)
		self.build(2 * ind + 2, mid + 1, high, arr)
		self.seg[ind] = min(self.seg[2 * ind + 1], self.seg[2 * ind + 2])

	def query(self, ind, low, high, l, r):
		if r < low or l > high:
			return sys.maxsize
		if low <= l and r >= high:
			return self.seg[ind]
		mid = low + high >> 1
		left = self.query(2 * ind + 1, 0, mid, l, r)
		right = self.query(2 * ind + 2, mid + 1, high, l, r)
		return min(left, right)

	def update(self, ind, low, high, i, val):
		if low == high:
			self.seg = val
			return
		mid = low + high >> 1
		if i <= mid:
			self.update(2 * ind + 1, low, mid, i, val)
		else:
			self.update(2 * ind + 1, mid + 1, high, i, val)
		self.seg[ind] = min(self.seg[2 * ind + 1], self.seg[2 * ind + 2])

def isPalindrome(s):
	i = 0
	j = len(s) - 1
	while i < j:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

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

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

def getStrs():
	return sys.stdin.readline().strip()

def StrList():
	list(sys.stdin.readline().strip())

def FloatList():
	lis = input().split()
	lis = list(map(float, lis))
	return lis

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

def findPrimePair(n):
	isPrime = [0] * (n + 1)
	SieveOfEratosthenes(n, isPrime)
	for i in range(0, n):
		if isPrime[i] and isPrime[n - i]:
			print(i, n - i)
			return

def query(ind, low, high, l, r, seg):
	if r < low or l > high:
		return info()
	if low <= l and r >= high:
		return self.seg[ind]
	mid = low + high >> 1
	left = self.query(2 * ind + 1, 0, mid, l, r, seg)
	right = self.query(2 * ind + 2, mid + 1, high, l, r, seg)
	return merge(left, right)

def merge(left, right):
	ans = info()
	ans.full = left.full + right.full + min(left.open, right.close)
	ans.open = left.open + right.open + min(left.open, right.close)
	ans.close = left.close + right.close + min(left.open, right.close)
	return ans

def build(ind, low, high, s, seg):
	if low == high:
		seg[ind] = info(s[low] == '(', s[low] == ')', 0)
		return
	mid = (low + high) // 2
	build(2 * ind + 1, low, mid, s, seg)
	build(2 * ind + 2, mid + 1, high, s, seg)
	seg[ind] = merge(seg[2 * ind + 1], seg[2 * ind + 2])

def countN(lis):
	ans = 0
	cnt = 0
	for i in range(len(lis) - 1, -1, -1):
		if lis[i] == 0:
			cnt += 1
		else:
			ans += cnt
	return ans

class Pair:

	def __init__(self, x, y, gcd):
		self.x = x
		self.y = y
		self.gcd = gcd

def Euclidean(a, b):
	if b == 0:
		return Pair(1, 0, a)
	dash = Euclidean(b, a % b)
	return Pair(dash.y, dash.x - a // b * dash.y, dash.gcd)

def chineseRemainder(a1, n1, a2, n2):
	p = Euclidean(n1, n2)
	x = p.x
	gcd = p.gcd
	if (a1 - a2) % gcd:
		return -1
	k = (a1 - a2) // gcd
	a = a1 - n1 * (k * x % n2 // gcd)
	lcm = n1 * n2 // gcd
	if a < 0:
		a += lcm
	return a
mdd = 998244353

def ncr(n, k, md):
	mod = 998244353
	tab = [[0 for _ in range(k + 1)] for i in range(n + 1)]
	for i in range(1, len(tab)):
		tab[i][0] = 1
	for i in range(1, len(tab)):
		for j in range(1, min(i + 1, len(tab[0]))):
			if i == 1 and j == 1:
				tab[i][j] = 1
			else:
				tab[i][j] = (tab[i - 1][j] + tab[i - 1][j - 1]) % mod
	return tab

def repeat(i, j, arr):
	if i > j:
		return
	cnt1 = i
	cnt2 = j
	while cnt1 < cnt2:
		(arr[cnt1], arr[cnt2]) = (arr[cnt2], arr[cnt1])
		cnt1 += 1
		cnt2 -= 1
	if i - 1 >= 0:
		ele = arr[i - 1]
		if ele > 0:
			s = int(sqrt(ele - 1)) + 1
			first = s * s - ele
			repeat(first, i - 1, arr)
	return
spf = []

def makeSeive(n):
	for i in range(n + 1):
		spf.append(i)

def seive(n):
	s = int(sqrt(n + 1))
	for i in range(2, s + 1):
		if spf[i] == i:
			for j in range(i * i, n + 1, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = set()
	while x != 1:
		ret.add(spf[x])
		x = x // spf[x]
	return ret

def zFunc(patt, txt):
	st = patt + '#' + txt
	zArray = [0 for _ in range(len(st))]
	l = 0
	r = 0
	for i in range(1, len(st)):
		if r >= i:
			zArray[i] = min(r - i + 1, zArray[i - l])
		while i + zArray[i] < len(st) and st[zArray[i]] == st[zArray[i] + i]:
			zArray[i] += 1
		if zArray[i] + i - 1 > r:
			l = i
			r = i + zArray[i] - 1
	return zArray.count(len(patt))

def kmp(txt, patt):
	newString = patt + '#' + txt
	freqCount = 0
	freqArray = [0 for _ in range(len(newString))]
	i = 1
	length = 0
	while i < len(newString):
		if newString[i] == newString[length]:
			length += 1
			freqArray[i] = length
			i += 1
		elif length > 0:
			length = freqArray[length - 1]
		else:
			freqArray[i] = 0
			i += 1
	for i in freqArray:
		if i == len(patt):
			freqCount += 1
	return freqCount

def getLPS(s):
	st = '@#' + '#'.join(s) + '#&'
	c = 0
	r = 0
	lps = [0] * len(st)
	for i in range(1, len(st) - 1):
		mirror = c - (i - c)
		if i < r and mirror >= 0:
			lps[i] = min(lps[mirror], r - i)
		while st[i + lps[i] + 1] == st[i - lps[i] - 1]:
			lps[i] += 1
		if i + lps[i] > r:
			r = i + lps[i]
			c = i
	return max(lps)
fact = [1 for _ in range(100002)]
mod = 10 ** 9 + 7

def getFact(n):
	for i in range(1, n + 1):
		fact[i] = fact[i - 1] * i % mod

def getInv(word):
	num = math.factorial(len(word))
	for v in Counter(word).values():
		num = num * pow(math.factorial(v), mod - 2, mod) % mod
	return int(num) % (10 ** 9 + 7)

def subarrayXor(arr, n, m):
	HashTable = defaultdict(bool)
	HashTable[0] = 1
	count = 0
	curSum = 0
	for i in arr:
		curSum ^= i
		if HashTable[curSum ^ m]:
			count += HashTable[curSum ^ m]
		HashTable[curSum] += 1
	return count

def get2dPrefixSum(matrix, mid=0):
	n = len(matrix)
	m = len(matrix[0])
	prefix = [[0 for _ in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
	return prefix

def get2dPrefixSumCnt(matrix, mid=0):
	n = len(matrix)
	m = len(matrix[0])
	prefix = [[0 for _ in range(m + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
	return prefix

def getSumRange(r1, c1, r2, c2, prefix):
	cnt = prefix[r2][c2] - prefix[r2][c1 - 1] - prefix[r1 - 1][c2] + prefix[r1 - 1][c1 - 1]
	return cnt

def getPrefix(arr):
	prefix = [0]
	for i in arr:
		prefix.append(prefix[-1] + i)
	return prefix

def getInv(arr):
	cnt = 0
	ans = []
	for i in arr:
		ind = bisect_right(ans, i)
		cnt += len(ans) - ind
		insort(ans, i)
	return cnt
M = 10 ** 5

def getFactors(x):
	temp = []
	k = 1
	while k * k <= x:
		if x % k == 0:
			temp.append(k)
			if k * k != x:
				temp.append(x // k)
		k += 1
	return temp

def grayCode(n):
	if not n:
		return [0]
	res = [0, 1]
	for i in range(2, n + 1):
		for j in range(len(res) - 1, -1, -1):
			res.append(res[j] | 1 << i - 1)
	return res

def threeSum(nums, target):
	ans = -1
	d = dict()
	for (i, j) in enumerate(nums):
		d[j] = i + 1
	nums.sort()
	for i in range(len(nums) - 2):
		low = i + 1
		high = len(nums) - 1
		while low < high:
			s = nums[i] + nums[low] + nums[high]
			if s == target:
				print(d[nums[low]], d[nums[high]], d[nums[i]])
				return
				low += 1
				high -= 1
			elif s < 0:
				low = low + 1
			else:
				high -= 1
	print('IMPOSSIBLE')
	return

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

def FuckCF():
	(n, m) = getInts()
	lis = IntList()
	prefix = [lis[0]]
	for i in lis[1:]:
		prefix.append(gcd(prefix[-1], i))
	suffix = [lis[-1]]
	for i in lis[::-1][1:]:
		suffix.append(gcd(suffix[-1], i))
	suffix = suffix[::-1]
	for _ in range(m):
		(l, r) = getInts()
		l -= 1
		if l == 0:
			print(suffix[r])
		elif r == n:
			print(prefix[l - 1])
		else:
			print(gcd(prefix[l - 1], suffix[r]))
t = 1
t = int(input())
for i in range(t):
	FuckCF()


pre = [0] * 100005
sff = [0] * 100005
t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
while t:
	t -= 1
	(n, q) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	pre[0] = sff[n + 1] = 0
	for i in range(1, n + 1):
		pre[i] = gcd(pre[i - 1], arr[i - 1])
	for i in range(n, 0, -1):
		sff[i] = gcd(sff[i + 1], arr[i - 1])
	while q:
		q -= 1
		(l, r) = map(int, input().split(' '))
		print(gcd(pre[l - 1], sff[r + 1]))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for case in range(t):
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	pre = [0] * (n + 1)
	suff = [0] * (n + 1)
	for i in range(1, n + 1):
		pre[i] = gcd(pre[i - 1], arr[i - 1])
	for i in range(n, 0, -1):
		suff[i - 1] = gcd(suff[i], arr[i - 1])
	for i in range(q):
		(l, r) = list(map(int, input().split()))
		print(gcd(pre[l - 1], suff[r]))


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for z in range(int(input())):
	(n, q) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	p = [1] * n
	g = a[0]
	for i in range(1, n):
		p[i] = g
		g = gcd(g, a[i])
	g = a[n - 1]
	s = [1] * n
	for i in range(n - 2, -1, -1):
		s[i] = g
		g = gcd(g, a[i])
	for i in range(q):
		(l, r) = [int(x) - 1 for x in input().split()]
		if l == 0:
			print(s[r])
			continue
		if r == n - 1:
			print(p[l])
			continue
		print(gcd(p[l], s[r]))


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	return a if b == 0 else gcd(b, a % b)
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	(lg, rg) = ([0] * (n + 2), [0] * (n + 2))
	lg[0] = 0
	rg[-1] = 0
	for i in range(1, n + 1):
		lg[i] = gcd(a[i - 1], lg[i - 1])
	for i in range(n, 0, -1):
		rg[i] = gcd(a[i - 1], rg[i + 1])
	for q1 in range(q):
		(l, r) = map(int, input().split())
		print(gcd(lg[l - 1], rg[r + 1]))


import math
import sys
from collections import Counter, defaultdict
from bisect import bisect_left
mod = 1000000007

def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())

def main():
	try:
		l_to_r = [lst[0]]
		r_to_l = [lst[-1]]
		for i in range(1, n):
			x = math.gcd(l_to_r[-1], lst[i])
			l_to_r.append(x)
		for i in range(n - 2, -1, -1):
			x = math.gcd(r_to_l[-1], lst[i])
			r_to_l.append(x)
		r_to_l = [0] + r_to_l[::-1] + [0]
		l_to_r = [0] + l_to_r + [0]
		for pair in range(q):
			(l, r) = integer_list()
			ans = math.gcd(l_to_r[l - 1], r_to_l[r + 1])
			print(ans)
	except Exception as e:
		print(e)
t = int(input())
for _ in range(t):
	(n, q) = integer_list()
	lst = integer_list()
	main()


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
t = int(input())
while t:
	(n, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	pre = [0] * (n + 1)
	post = [0] * (n + 2)
	for i in range(1, n + 1):
		pre[i] = gcd(pre[i - 1], a[i - 1])
	for j in range(n, 0, -1):
		post[j] = gcd(post[j + 1], a[j - 1])
	for _ in range(q):
		(x, y) = map(int, input().split())
		print(gcd(pre[x - 1], post[y + 1]))
	t -= 1


import math
testcase = int(input())
while testcase:
	(n, queries) = map(int, input().split())
	lists = list(map(int, input().split()))
	forward = [0] * (n + 1)
	backward = [0] * (n + 1)
	for i in range(1, n + 1):
		forward[i] = math.gcd(forward[i - 1], lists[i - 1])
	for i in range(n - 1, -1, -1):
		backward[i] = math.gcd(backward[i + 1], lists[i])
	while queries:
		(l, r) = map(int, input().split())
		print(math.gcd(forward[l - 1], backward[r]))
		queries -= 1
	testcase -= 1


import math
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(n, q) = map(int, stdin.readline().split())
	l = list(map(int, stdin.readline().split()))
	suff = [l[-1]]
	pre = [l[0]]
	for i in range(1, n):
		pre.append(math.gcd(pre[-1], l[i]))
	for i in range(n - 2, -1, -1):
		suff.append(math.gcd(suff[-1], l[i]))
	suff = suff[::-1]
	pre = [0] + pre
	suff = suff + [0]
	for i in range(q):
		(l, r) = map(int, stdin.readline().split())
		print(math.gcd(pre[l - 1], suff[r]))


from math import gcd
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	lst = [int(i) for i in input().split()]
	lst1 = [0] * n
	lst2 = [0] * n
	for i in range(0, n):
		if i == 0:
			lst1[i] = lst[i]
		else:
			lst1[i] = gcd(lst1[i - 1], lst[i])
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			lst2[i] = lst[i]
		else:
			lst2[i] = gcd(lst2[i + 1], lst[i])
	for __ in range(0, m):
		(a, b) = [int(i) for i in input().split()]
		a = a - 1
		b = b - 1
		if a > 0 and b + 1 < n:
			print(gcd(lst1[a - 1], lst2[b + 1]))
		elif b + 1 < n:
			print(lst2[b + 1])
		else:
			print(lst1[a - 1])


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	pl = [0]
	ps = [0]
	for i in range(n):
		pl.append(gcd(pl[-1], l[i]))
		ps.append(gcd(ps[-1], l[n - i - 1]))
	ps = ps[::-1]
	for i in range(q):
		(a, b) = map(int, input().split())
		print(gcd(pl[a - 1], ps[b]))


import sys
input = sys.stdin.readline

def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	q = int(l[1])
	l = input().split()
	li = [int(i) for i in l]
	pref = []
	num = li[0]
	for i in range(n):
		num = gcd(num, li[i])
		pref.append(num)
	suff = []
	num = li[-1]
	for i in range(n - 1, -1, -1):
		num = gcd(num, li[i])
		suff.append(num)
	suff.reverse()
	for i in range(q):
		l = input().split()
		r = int(l[1])
		l = int(l[0])
		l -= 1
		r -= 1
		if l - 1 >= 0 and r + 1 < n:
			g = pref[l - 1]
			g = gcd(g, suff[r + 1])
			print(g)
		elif l == 0:
			print(suff[r + 1])
		else:
			print(pref[l - 1])


def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	elif b > a:
		return gcd(b, a)
	else:
		return gcd(b, a % b)
tc = int(input())
for _ in range(tc):
	(n, q) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	arr.insert(0, 0)
	arr.append(0)
	(prefix, sufix) = ([0] * (n + 1), [0] * (n + 2))
	for i in range(1, n + 1):
		ele = arr[i]
		prefix[i] = gcd(prefix[i - 1], ele)
	for i in range(n, 0, -1):
		ele = arr[i]
		sufix[i] = gcd(sufix[i + 1], ele)
	for _ in range(q):
		(l, r) = map(int, input().split(' '))
		print(gcd(prefix[l - 1], sufix[r + 1]))


import math
for t in range(int(input())):
	(n, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	x = [0] * (n + 1)
	y = [0] * (n + 1)
	b = a[0]
	for i in range(1, n + 1):
		b = math.gcd(b, a[i - 1])
		x[i] = b
	b = a[-1]
	for i in range(n - 1, -1, -1):
		b = math.gcd(b, a[i])
		y[i] = b
	for i in range(q):
		(l, r) = map(int, input().split())
		print(math.gcd(x[l - 1], y[r]))


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	gcd_left = [0]

	def gcd(a, b):
		if b == 0:
			return a
		else:
			return gcd(b, a % b)
	for i in range(len(arr)):
		gcd_left.append(gcd(gcd_left[-1], arr[i]))
	gcd_right = [0]
	for i in range(-1, -len(arr) - 1, -1):
		gcd_right.append(gcd(gcd_right[-1], arr[i]))
	gcd_right = gcd_right[::-1]
	for _ in range(q):
		(l, r) = map(int, input().split())
		print(gcd(gcd_left[l - 1], gcd_right[r]))


import math
for t in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list()
	arr = [0] + list(map(int, input().split()))
	(pre, suf) = ([0] * (n + 1), [0] * (n + 2))
	for i in range(1, n + 1):
		pre[i] = math.gcd(pre[i - 1], arr[i])
	for i in range(n, 0, -1):
		suf[i] = math.gcd(suf[i + 1], arr[i])
	for _ in range(q):
		(l, r) = map(int, input().split())
		print(math.gcd(pre[l - 1], suf[r + 1]))


import math
t = int(input())
for tc in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	left = [0] * (n + 1)
	right = [0] * (n + 1)
	for i in range(1, n + 1):
		left[i] = math.gcd(left[i - 1], a[i - 1])
	for i in range(n - 1, -1, -1):
		right[i] = math.gcd(right[i + 1], a[i])
	for i in range(q):
		(l, r) = map(int, input().split())
		print(math.gcd(left[l - 1], right[r]))


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def gcd(x, y):
	while y > 0:
		(x, y) = (y, x % y)
	return x
t = ri()
for test in range(t):
	(n, q) = rl()
	arr = rl()
	prefix = [0] * (n + 2)
	suffix = [0] * (n + 2)
	for i in range(n):
		prefix[i + 1] = gcd(prefix[i], arr[i])
	for i in range(n, 0, -1):
		suffix[i] = gcd(suffix[i + 1], arr[i - 1])
	for i in range(q):
		(l, r) = rl()
		ans = gcd(prefix[l - 1], suffix[r + 1])
		print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for t in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	l_gcd = [0] * (n + 1)
	for i in range(1, n + 1):
		l_gcd[i] = gcd(arr[i - 1], l_gcd[i - 1])
	r_gcd = [0] * (n + 1)
	for i in range(-2, -n - 2, -1):
		r_gcd[i] = gcd(arr[i + 1], r_gcd[i + 1])
	for i in range(q):
		(l, r) = map(int, input().split())
		print(gcd(l_gcd[l - 1], r_gcd[r]))


import math
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr1 = list(map(int, input().split()))
	pl = [0]
	ps = [0]
	for i in range(n):
		pl.append(math.gcd(pl[-1], arr1[i]))
		ps.append(math.gcd(ps[-1], arr1[n - i - 1]))
	ps = ps[::-1]
	for i in range(q):
		(l, r) = map(int, input().split())
		print(math.gcd(pl[l - 1], ps[r]))


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		(n, q) = rv(int)
		a = ra(int)
		p = [0 for _ in range(n)]
		s = [0 for _ in range(n)]
		pg = 0
		sg = 0
		for i in range(n):
			pg = gcd(pg, a[i])
			sg = gcd(sg, a[n - 1 - i])
			p[i] = pg
			s[n - 1 - i] = sg
		for _ in range(q):
			(l, r) = rv(int)
			(l, r) = (l - 1, r - 1)
			g1 = 0
			if l != 0:
				g1 = p[l - 1]
			g2 = 0
			if r < n - 1:
				g2 = s[r + 1]
			print(gcd(g1, g2))
main()


import math
n = int(input())
for i in range(n):
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	gcd_left = [0]
	for i in range(len(arr)):
		gcd_left.append(math.gcd(gcd_left[-1], arr[i]))
	gcd_right = [0]
	for i in range(-1, -len(arr) - 1, -1):
		gcd_right.append(math.gcd(gcd_right[-1], arr[i]))
	gcd_right = gcd_right[::-1]
	for i in range(q):
		(left, right) = list(map(int, input().split()))
		print(math.gcd(gcd_left[left - 1], gcd_right[right]))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	s = list(map(int, input().split()))
	pre = [0 for i in range(n + 1)]
	suf = [0 for i in range(n + 1)]
	pre[0] = 0
	suf[-1] = 0
	for i in range(1, len(pre)):
		pre[i] = gcd(pre[i - 1], s[i - 1])
	for i in range(len(suf) - 2, -1, -1):
		suf[i] = gcd(suf[i + 1], s[i])
	for i in range(q):
		(l, r) = map(int, input().split())
		print(gcd(pre[l - 1], suf[r]))


pre = [0] * 100005
suf = [0] * 100005

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	a = [0]
	a.extend(l)
	pre[0] = suf[n + 1] = 0
	for i in range(1, n + 1):
		pre[i] = gcd(pre[i - 1], a[i])
	for i in range(n, 0, -1):
		suf[i] = gcd(suf[i + 1], a[i])
	for i in range(q):
		(l, r) = map(int, input().split(' '))
		ans = gcd(pre[l - 1], suf[r + 1])
		print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(n, q) = map(int, input().strip().split())
	arr = [int(i) for i in input().split()]
	prefix_gcd = [0] * n
	prefix_gcd[0] = arr[0]
	for i in range(1, n):
		prefix_gcd[i] = gcd(arr[i], prefix_gcd[i - 1])
	suffix_gcd = [0] * n
	suffix_gcd[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		suffix_gcd[i] = gcd(arr[i], suffix_gcd[i + 1])
	for i in range(q):
		(l, r) = map(int, input().strip().split())
		(l, r) = (l - 1, r - 1)
		left = prefix_gcd[l - 1] if l - 1 >= 0 else None
		right = suffix_gcd[r + 1] if r + 1 < n else None
		if left and right:
			print(gcd(left, right))
		elif left and (not right):
			print(left)
		else:
			print(right)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def cummulative_gcd(arr, n):
	cummf.append(0)
	for i in range(n):
		cummf.append(gcd(arr[i], cummf[i]))
	arr.reverse()
	cummr.append(0)
	for j in range(n):
		cummr.append(gcd(arr[j], cummr[j]))
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	cummf = []
	cummr = []
	array = cummulative_gcd(a, n)
	for _ in range(q):
		(l, r) = map(int, input().split())
		res = gcd(cummf[l - 1], cummr[n - r])
		print(res)


n = int(input())
for i in range(n):

	def recr(a, b):
		if b == 0:
			return a
		return recr(b, a % b)
	(a, length) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	prefix = [0 for i in range(len(lis))]
	suffix = [0 for i in range(len(lis))]
	for i in range(len(prefix)):
		prefix[i] = recr(lis[i], prefix[i - 1])
	suffix[-1] = lis[-1]
	for i in range(len(lis) - 2, -1, -1):
		suffix[i] = recr(lis[i], suffix[i + 1])
	for i in range(length):
		(start, end) = list(map(int, input().split()))
		if start - 1 == 0:
			print(suffix[end])
		elif end == len(lis):
			print(prefix[start - 2])
		else:
			print(recr(prefix[start - 2], suffix[end]))


import sys
import math
T = int(sys.stdin.readline().rstrip())
for t in range(T):
	(N, Q) = list(map(int, sys.stdin.readline().rstrip().split()))
	arr = list(map(int, sys.stdin.readline().rstrip().split()))
	arr = [0] + arr
	fpc = (len(arr) + 10) * [0]
	bpc = (len(arr) + 10) * [0]
	for i in range(1, len(arr)):
		fpc[i] = math.gcd(fpc[i - 1], arr[i])
	for i in range(N, 0, -1):
		bpc[i] = math.gcd(bpc[i + 1], arr[i])
	for q in range(Q):
		(l, r) = list(map(int, sys.stdin.readline().rstrip().split()))
		print(math.gcd(fpc[l - 1], bpc[r + 1]))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	pre_gcd = [arr[0]]
	post_gcd = [arr[-1]]
	for i in range(1, n):
		a = arr[i]
		b = pre_gcd[i - 1]
		pre_gcd.append(gcd(a, b))
	for i in range(n - 2, -1, -1):
		a = post_gcd[n - 2 - i]
		b = arr[i]
		post_gcd.append(gcd(a, b))
	post_gcd.reverse()
	for i in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		g1 = 0
		g2 = 0
		if l != 0:
			g1 = pre_gcd[l - 1]
		if r != n - 1:
			g2 = post_gcd[r + 1]
		print(gcd(g1, g2))


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	prefix = [0] * n
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = gcd(prefix[i - 1], arr[i])
	suffix = [0] * n
	suffix[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		suffix[i] = gcd(suffix[i + 1], arr[i])
	for i in range(q):
		(l, r) = map(int, input().split())
		l = l - 1
		r = r - 1
		if l == 0:
			ans = suffix[r + 1]
		elif r == n - 1:
			ans = prefix[l - 1]
		else:
			ans = gcd(prefix[l - 1], suffix[r + 1])
		print(ans)


from math import gcd
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	pre = [0] * n
	suf = [0] * n
	pre[0] = arr[0]
	suf[-1] = arr[-1]
	for i in range(1, n):
		pre[i] = gcd(pre[i - 1], arr[i])
		suf[n - 1 - i] = gcd(suf[n - i], arr[n - 1 - i])
	for _ in range(q):
		(u, v) = map(int, input().split())
		if u - 2 >= 0 and v < n:
			print(gcd(pre[u - 2], suf[v]))
		elif u - 2 >= 0:
			print(pre[u - 2])
		else:
			print(suf[v])


import math
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	pahleka = [0] * n
	baadka = [0] * n
	for i in range(1, n):
		pahleka[i] = math.gcd(arr[i - 1], pahleka[i - 1])
	for i in range(n - 2, -1, -1):
		baadka[i] = math.gcd(arr[i + 1], baadka[i + 1])
	for _ in range(q):
		(L, R) = map(int, input().split())
		print(math.gcd(pahleka[L - 1], baadka[R - 1]))


import math
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	gcd1 = [a[0]] * n
	gcd2 = [a[-1]] * n
	for j in range(1, n):
		gcd1[j] = math.gcd(a[j], gcd1[j - 1])
	for k in range(n - 2, -1, -1):
		gcd2[k] = math.gcd(a[k], gcd2[k + 1])
	for z in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		if l == 0:
			print(gcd2[r + 1])
		elif r == n - 1:
			print(gcd1[l - 1])
		else:
			print(math.gcd(gcd1[l - 1], gcd2[r + 1]))


def gcd(a, b):
	while b > 0:
		temp = b
		b = a % b
		a = temp
	return a
t = int(input())
for test in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	a1 = [arr[0]]
	a2 = [arr[-1]]
	for i in range(1, n):
		num = a1[-1]
		num2 = arr[i]
		ans = gcd(num, num2)
		a1.append(ans)
	for j in range(1, n):
		i = n - j - 1
		num = a2[-1]
		num2 = arr[i]
		ans = gcd(num, num2)
		a2.append(ans)
	for i in range(q):
		(l, r) = map(int, input().split())
		l = l - 2
		r = n - r - 1
		ans1 = -1
		ans2 = -1
		if l == -1:
			ans1 = 0
		else:
			ans1 = a1[l]
		if r == -1:
			ans2 = 0
		else:
			ans2 = a2[r]
		print(gcd(ans1, ans2))


def gcd(m, n):
	if m == 0:
		return n
	else:
		return gcd(n % m, m)
for t in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [0] + list(map(int, input().split()))
	left = [0] * (n + 2)
	right = [0] * (n + 2)
	for i in range(1, n + 1):
		left[i] = gcd(left[i - 1], arr[i])
	for i in range(n, 0, -1):
		right[i] = gcd(arr[i], right[i + 1])
	for x in range(q):
		(l, r) = map(int, input().split())
		ans = gcd(left[l - 1], right[r + 1])
		print(ans)


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
I = sys.stdin.readline

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

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 gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def valid(row, col, rows, cols, rcross, lcross):
	return rows[row] == 0 and cols[col] == 0 and (rcross[col + row] == 0) and (lcross[col - row] == 0)

def div(n):
	tmp = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			cnt = 0
			while n % i == 0:
				n = n // i
				cnt += 1
			tmp.append((i, cnt))
	if n > 1:
		tmp.append((n, 1))
	return tmp

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		flag = True
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				flag = False
				break
		return flag

def s(b):
	ans = []
	while b > 0:
		tmp = b % 10
		ans.append(tmp)
		b = b // 10
	return ans

def main():
	ans = ''
	for _ in range(ii()):
		(n, q) = mi()
		a = li()
		queries = []
		for i in range(q):
			(l, r) = mi()
			queries.append((l, r))
		prefix = [a[0]]
		for i in range(1, n):
			prefix.append(gcd(prefix[-1], a[i]))
		suffix = [0] * n
		suffix[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			suffix[i] = gcd(suffix[i + 1], a[i])
		for i in queries:
			if i[0] == 1:
				print(suffix[i[1]])
			elif i[1] == n:
				print(prefix[i[0] - 2])
			else:
				tm = gcd(prefix[i[0] - 2], suffix[i[1]])
				print(tm)
main()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	a = [int(x) for x in input().split()]
	p = a[:]
	s = a[:]
	for i in range(1, n):
		p[i] = gcd(p[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		s[i] = gcd(s[i + 1], a[i])
	for i in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		g1 = 0
		g2 = 0
		if l != 0:
			g1 = p[l - 1]
		if r != n - 1:
			g2 = s[r + 1]
		print(gcd(g1, g2))


import math
t = int(input())
for _ in range(t):
	(n, q) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	gcd_l = [arr[0]] * n
	gcd_r = [arr[-1]] * n
	for i in range(1, n):
		gcd_l[i] = math.gcd(arr[i], gcd_l[i - 1])
	for i in range(n - 2, -1, -1):
		gcd_r[i] = math.gcd(arr[i], gcd_r[i + 1])
	for i in range(q):
		(l, r) = [int(x) for x in input().split()]
		l -= 1
		r -= 1
		if l == 0:
			print(gcd_r[r + 1])
		elif r == n - 1:
			print(gcd_l[l - 1])
		else:
			print(math.gcd(gcd_l[l - 1], gcd_r[r + 1]))


import sys, io, os, math, time
from math import ceil, log, gcd, inf, floor

def printlist(n):
	sys.stdout.write(' '.join(map(str, n)) + '\n')
printf = lambda n: sys.stdout.write(str(n) + '\n')

def printns(n):
	sys.stdout.write(str(n))

def intinp():
	return int(sys.stdin.readline())

def strinp():
	return sys.stdin.readline()

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

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

def main():
	tc = intinp()
	while tc:
		(n, q) = mulinp()
		a = arrinp()
		forward = [0] * (n + 10)
		backward = [0] * (n + 10)
		for i in range(1, n + 1):
			forward[i] = gcd(forward[i - 1], a[i - 1])
		it = n
		while it:
			backward[it] = gcd(backward[it + 1], a[it - 1])
			it -= 1
		while q:
			(l, r) = mulinp()
			print(gcd(forward[l - 1], backward[r + 1]))
			q -= 1
		tc -= 1
main()


from sys import stdin, stdout
import bisect
import math

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

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

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

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

def soe(limit):
	l = [1] * (limit + 1)
	pp = [0] * (limit + 1)
	prime = []
	l[0] = 0
	l[1] = 0
	c = 0
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i] == 1:
			c += 1
		if l[c] == 1:
			pp[i] = 1
	for i in range(1, limit + 1):
		pp[i] += pp[i - 1]
	return pp

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def solve():
	(n, k) = mp()
	l = li()
	pre = [l[0]]
	for i in range(1, n):
		pre.append(gcd(pre[-1], l[i]))
	suf = [l[-1]]
	for i in range(n - 2, -1, -1):
		suf.append(gcd(suf[-1], l[i]))
	suf = suf[::-1]
	pre = [0] + pre
	suf = suf + [0]
	for i in range(k):
		(a, b) = mp()
		print(gcd(pre[a - 1], suf[b]))
for _ in range(inp()):
	solve()


import sys
from math import gcd
for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	leftArr = []
	rghtArr = []
	val = 0
	for i in range(n):
		val = gcd(val, a[i])
		leftArr.append(val)
	val = 0
	for i in range(n - 1, -1, -1):
		val = gcd(val, a[i])
		rghtArr.append(val)
	rghtArr.reverse()
	while q > 0:
		q -= 1
		(l, r) = list(map(int, input().split()))
		l -= 1
		r -= 1
		if l == 0:
			ans_l = 0
		else:
			ans_l = leftArr[l - 1]
		if r == n - 1:
			ans_r = 0
		else:
			ans_r = rghtArr[r + 1]
		print(gcd(ans_l, ans_r))


from math import gcd
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	a = [0] + a
	r = [0] * (n + 1)
	s = [0] * (n + 2)
	r[0] = a[0]
	for i in range(1, n + 1):
		r[i] = gcd(r[i - 1], a[i])
	for i in range(n, 0, -1):
		s[i] = gcd(s[i + 1], a[i])
	for i in range(q):
		(x, y) = map(int, input().split())
		print(gcd(r[x - 1], s[y + 1]))


def gcd(a, b):
	if b == 0:
		return a
	elif a == 0:
		return b
	else:
		if a < b:
			(a, b) = (b, a)
		if a % b == 0:
			return b
		while a % b != 0:
			return gcd(b, a % b)
x = int(input())
for i in range(x):
	(n, q) = input().split()
	m = input().split()
	n = int(n)
	lit = []
	prf = [0] * (n + 1)
	suff = [0] * (n + 2)
	for k in m:
		lit.append(int(k))
	for p in range(1, n + 1):
		prf[p] = gcd(prf[p - 1], lit[p - 1])
	for u in range(n, 0, -1):
		suff[u] = gcd(suff[u + 1], lit[u - 1])
	for j in range(int(q)):
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		print(gcd(suff[r + 1], prf[l - 1]))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for i in range(t):
	(n, q) = tuple(map(int, input().split()))
	a = list(map(int, input().split()))
	pre = [0] * (n + 1)
	pre[1] = a[0]
	for j in range(2, n + 1):
		pre[j] = gcd(a[j - 1], pre[j - 1])
	suf = [0] * (n + 1)
	suf[n - 1] = a[-1]
	for j in range(n - 2, -1, -1):
		suf[j] = gcd(a[j], suf[j + 1])
	for _ in range(q):
		(l, r) = tuple(map(int, input().split()))
		print(gcd(pre[l - 1], suf[r]))


import math
t = int(input())
while t > 0:
	t -= 1
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	mem = []
	mem.append(arr[0])
	for i in range(1, len(arr)):
		mem.append(math.gcd(mem[i - 1], arr[i]))
	memsuff = []
	memsuff.append(arr[len(arr) - 1])
	for i in range(len(arr) - 2, -1, -1):
		memsuff.append(math.gcd(memsuff[len(arr) - i - 2], arr[i]))
	memsuff = memsuff[::-1]
	while q > 0:
		q -= 1
		(l, r) = list(map(int, input().split()))
		if l == 1:
			print(memsuff[r])
		elif r == n:
			print(mem[l - 2])
		else:
			print(math.gcd(mem[l - 2], memsuff[r]))


from math import gcd
t = int(input())
while t:
	(n, q) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.insert(0, 0)
	gcdForward = [0] * (n + 1)
	gcdBackward = [0] * (n + 2)
	for i in range(1, n + 1):
		gcdForward[i] = gcd(gcdForward[i - 1], arr[i])
	for i in range(n, 0, -1):
		gcdBackward[i] = gcd(gcdBackward[i + 1], arr[i])
	while q:
		(l, r) = [int(i) for i in input().split()]
		print(gcd(gcdForward[l - 1], gcdBackward[r + 1]))
		q -= 1
	t -= 1


t = int(input(''))
for i in range(t):
	out = []
	(n, q) = map(int, input('').split())
	pre = []
	suf = []
	x = list(map(int, input('').split()))
	a = x[0]
	pre.append(a)
	for j in range(1, n):
		b = x[j]
		while b != 0:
			(a, b) = (b, a % b)
		pre.append(a)
	a = x[-1]
	suf.append(a)
	for j in range(n - 1, -1, -1):
		b = x[j]
		while b != 0:
			(a, b) = (b, a % b)
		suf.append(a)
	suf.reverse()
	for j in range(q):
		(l, r) = map(int, input('').split())
		if l == 1:
			out.append(suf[r])
		elif r == n:
			out.append(pre[l - 2])
		else:
			a = pre[l - 2]
			b = suf[r]
			if b == 0 or a == 0:
				out.append(a + b)
			else:
				while b != 0:
					(a, b) = (b, a % b)
				out.append(a)
	for i in out:
		print(i)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	arr = list(map(int, input().split()))
	prefix = [0] * N
	for i in range(1, N):
		prefix[i] = gcd(prefix[i - 1], arr[i - 1])
	suffix = [0] * N
	for i in reversed(range(N - 1)):
		suffix[i] = gcd(suffix[i + 1], arr[i + 1])
	for _ in range(Q):
		(L, R) = map(int, input().split())
		print(gcd(prefix[L - 1], suffix[R - 1]))


def gcd(a, b):
	if a == b:
		return a
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def arrgcd(arr):
	if len(arr) == 1:
		return
	for i in range(1, len(arr)):
		arr[i] = gcd(arr[i], arr[i - 1])
case = int(input())
for r in range(case):
	(n, q) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	rarr = list(reversed(arr))
	arrgcd(arr)
	arrgcd(rarr)
	rarr.reverse()
	for qq in range(q):
		(l, r) = [int(x) for x in input().split()]
		if l == 1:
			print(rarr[r])
			continue
		if r == n:
			print(arr[l - 2])
			continue
		print(gcd(arr[l - 2], rarr[r]))


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	queries = []
	for k in range(q):
		queries.append(list(map(int, input().split())))
	prefix = [0] * len(a)
	suffix = [0] * len(a)
	prefix[0] = a[0]
	for i in range(1, len(a)):
		prefix[i] = gcd(prefix[i - 1], a[i])
	suffix[len(a) - 1] = a[len(a) - 1]
	for i in range(len(a) - 2, -1, -1):
		suffix[i] = gcd(max(suffix[i + 1], a[i]), min(suffix[i + 1], a[i]))
	for i in queries:
		l = i[0] - 1
		r = i[1] - 1
		if l == 0:
			ans = suffix[r + 1]
		elif r == len(a) - 1:
			ans = prefix[l - 1]
		else:
			ans = gcd(max(prefix[l - 1], suffix[r + 1]), min(prefix[l - 1], suffix[r + 1]))
		print(ans)


def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	while b > 0:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	arr = [0] + [int(i) for i in input().split()]
	pre = [0] * (n + 1)
	suf = [0] * (n + 2)
	for i in range(1, n + 1):
		pre[i] = gcd(pre[i - 1], arr[i])
	for i in range(n, 0, -1):
		suf[i] = gcd(suf[i + 1], arr[i])
	for o in range(q):
		(l, r) = map(int, input().split())
		print(gcd(pre[l - 1], suf[r + 1]))


import sys
import math
from sys import stdin, stdout

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

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

def get_string():
	return sys.stdin.readline().strip()

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def calculatesuffixSuffix(arr, prefix, suffix):
	prefix[1] = arr[0]
	suffix[len(arr) - 1] = arr[-1]
	j = len(arr) - 2
	for i in range(2, len(arr)):
		prefix[i] = gcd(prefix[i - 1], arr[i - 1])
	while j >= 0:
		suffix[j] = gcd(suffix[j + 1], arr[j])
		j -= 1

def main():
	for _ in range(int(input())):
		(n, q) = get_ints_in_variables()
		arr = get_ints_in_list()
		prefix = [0 for _ in range(n)]
		suffix = [0 for _ in range(n)]
		calculatesuffixSuffix(arr, prefix, suffix)
		for _ in range(q):
			(l, r) = get_ints_in_variables()
			if l == 1:
				print(suffix[r])
			elif r == len(arr):
				print(prefix[l - 1])
			else:
				print(gcd(prefix[l - 1], suffix[r]))
main()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	li = list(map(int, input().split()))
	pre = []
	a = li[0]
	pre.append(a)
	for i in range(1, n):
		b = li[i]
		while b != 0:
			(a, b) = (b, a % b)
		pre.append(a)
	a = li[-1]
	suf = []
	for i in range(n - 1, -1, -1):
		b = li[i]
		while b != 0:
			(a, b) = (b, a % b)
		suf.append(a)
	suf.reverse()
	for i in range(q):
		(l, r) = map(int, input().split())
		if l == 1:
			print(suf[r])
		elif r == n:
			print(pre[l - 2])
		else:
			a = pre[l - 2]
			b = suf[r]
			while b != 0:
				(a, b) = (b, a % b)
			print(a)


def hcf(a, b):
	if a == 0:
		return b
	else:
		return hcf(b % a, a)
for t in range(int(input())):
	(N, Q) = map(int, input().split())
	arr = [0]
	arr = arr + list(map(int, input().split()))
	l = [0] * (N + 2)
	r = [0] * (N + 2)
	for i in range(1, N + 1):
		l[i] = hcf(l[i - 1], arr[i])
	for i in range(N, 0, -1):
		r[i] = hcf(r[i + 1], arr[i])
	for i in range(Q):
		(left, right) = map(int, input().split())
		print(hcf(l[left - 1], r[right + 1]))


def findGCD(num1, num2):
	snum = min(num1, num2)
	lnum = max(num1, num2)
	if snum == 0:
		return lnum
	while lnum % snum != 0:
		temp = snum
		snum = lnum % snum
		lnum = temp
	return snum
t = int(input())
while t:
	(n, q) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	arr.insert(0, 0)
	gcdForward = [0] * (n + 1)
	gcdBackward = [0] * (n + 2)
	for i in range(1, n + 1):
		gcdForward[i] = findGCD(gcdForward[i - 1], arr[i])
	for i in range(n, 0, -1):
		gcdBackward[i] = findGCD(gcdBackward[i + 1], arr[i])
	while q:
		(l, r) = [int(i) for i in input().split()]
		print(findGCD(gcdForward[l - 1], gcdBackward[r + 1]))
		q -= 1
	t -= 1