You are an evil sorcerer at a round table with $N$ sorcerers (including yourself). You can cast $M$ spells which have distinct powers $p_1, p_2, \ldots, p_M$.
You may perform the following operation any number of times (possibly zero):
- Assign a living sorcerer to each positive integer cyclically to your left starting from yourself ― the closest living sorcerer to your left is assigned to $1$, the next living sorcerer to the left is assigned to $2$ and so on. Note that each living sorcerer (including yourself) is assigned to an infinite number of integers.
- Choose a spell $j$ (possibly a spell you have chosen before) and kill the living sorcerer assigned to $p_j$. You may not cast a spell to kill yourself. 

What is the maximum number of sorcerers you can kill using zero or more operations?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $M$.
- The second line contains $M$ space-separated integers $p_1, p_2, \ldots, p_M$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum number of sorcerers you can kill.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le N \le 10^9$
- $1 \le M \le 3 \cdot 10^5$
- $1 \le p_i \le 10^9$ for each valid $i$
- $p_1, p_2, \ldots, p_N$ are pairwise distinct
- the sum of $M$ over all test cases does not exceed $3 \cdot 10^5$

-----Example Input-----
5
4 1
5
6 2
2 4
1 4
7 16 8 29
1000000000 1
998244353
1 1
20201220

-----Example Output-----
3
4
0
1755647
0

-----Explanation-----
Example case 1: The initial state is shown in the figure from the statement. We can first use spell $1$ and kill the $5$-th sorcerer to our left, i.e. sorcerer $2$. Now there are $3$ living sorcerers and the state is as shown in the following figure:

We can use spell $1$ again and kill the current $5$-th living sorcerer to our left, i.e. sorcerer $4$. Now there are $2$ living sorcerers and the state is:

Finally, we can use spell $1$ again and kill the only other living sorcerer, i.e. sorcerer $3$. Now, none of the other sorcerers are alive. As we cannot cast a spell to kill ourselves, we cannot improve the answer any further.
Example case 2: We can perform $4$ operations using the spell $p_1 = 2$ each time. We can also instead use $p_2 = 4$ in the first two operations and $p_1 = 2$ in the last two operations. Note that there may be multiple valid sequences of operations that lead to the best answer.
Example case 3: We cannot perform any operations using any of the given spells, so we are unable to kill any sorcerers.
Example case 4: We can perform $1,755,647$ operations, each of them using the spell $p_1 = 998,244,353$.

Source: codechef | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def gcd_arr(l):
	num1 = l[0]
	num2 = l[1]
	gcd = find_gcd(num1, num2)
	for i in range(2, len(l)):
		gcd = find_gcd(gcd, l[i])
	return gcd

def factors(n):
	if n == 0:
		return 1
	x = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			x.append(i)
			x.append(n // i)
	return x
for t in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	hcf = 0
	if m > 1:
		hcf = gcd_arr(p)
	else:
		hcf = p[0]
	fact = factors(hcf)
	fact.sort(reverse=True)
	final = 0
	for i in fact:
		if i <= n:
			final = n - i
			break
	print(final)


def CommonSpells(x, y):
	if y == 0:
		return x
	return CommonSpells(y, x % y)
for t in range(int(input())):
	(n, m) = map(int, input().split())
	spells = list(map(int, input().split()))
	common = 0
	for i in range(m):
		common = CommonSpells(common, spells[i])
	if common > n:
		valid = 0
		for i in range(1, common):
			if common % i == 0 and i <= n:
				valid = max(valid, i)
		common = valid
	print(n - common)


import math

def factor(a):
	for x in range(2, a):
		if a % x == 0:
			return a / x

def factors(n):
	if n == 0:
		return 1
	x = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			x.append(i)
			x.append(n // i)
	x.sort(reverse=True)
	return x

def gcd(a, b):
	if b > a:
		(a, b) = (b, a)
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	spells = list(map(int, input().split()))
	ans = 0
	for spell in spells:
		ans = gcd(ans, spell)
	fact = factors(ans)
	for f in fact:
		if f <= n:
			print(n - f)
			break


from functools import reduce
import math

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

def gcd(l):
	return reduce(lambda x, y: find_gcd(x, y), l)

def div(g, n):
	m = 0
	for i in range(1, math.floor(math.sqrt(g)) + 1):
		if g % i == 0:
			if i <= n:
				m = max(m, i)
			if g // i <= n:
				m = max(m, g // i)
	return m
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	g = gcd(p)
	if g > n:
		g = div(g, n)
	print(n - g)


try:

	def gcd_fd(i, j):
		while j:
			(i, j) = (j, i % j)
		return i

	def gcd_l(t):
		num = t[0]
		k = t[1]
		gcd = gcd_fd(num, k)
		for i in range(2, len(t)):
			gcd = gcd_fd(gcd, t[i])
		return gcd

	def fact(num1):
		if num1 == 0:
			return 1
		a = []
		for j in range(1, int(num1 ** (1 / 2)) + 1):
			if num1 % j == 0:
				a.append(j)
				a.append(num1 // j)
		return a
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		p = 0
		ans = 0
		if m > 1:
			p = gcd_l(a)
		else:
			p = a[0]
		fac = fact(p)
		fac.sort(reverse=True)
		for i in fac:
			if i <= n:
				ans = n - i
				break
		print(ans)
except:
	pass


from math import gcd

def gcd_list(l):
	g = gcd(l[0], l[1])
	for i in range(2, len(l)):
		g = gcd(g, l[i])
	return g

def factor(n):
	fact = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			fact.append(i)
			if n // i not in fact:
				fact.append(n // i)
	fact.sort(reverse=True)
	return fact

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		p = list(map(int, input().split()))
		if m == 1:
			g1 = p[0]
		else:
			g1 = gcd_list(p)
		factors = factor(g1)
		ans = 0
		for i in factors:
			if i <= n:
				ans = n - i
				break
		print(ans)
main()


from math import gcd

def factor(n):
	fact = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			fact.append(i)
			fact.append(n // i)
	fact.sort()
	fact.reverse()
	return fact
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	if m == 1:
		g = l[0]
		f = factor(g)
		for value in f:
			if value <= n:
				print(n - value)
				break
	else:
		g = gcd(l[0], l[1])
		for i in range(2, m):
			g = gcd(g, l[i])
		f = factor(g)
		for value in f:
			if value <= n:
				print(n - value)
				break


import math

def hcfnaive(a, b):
	if b == 0:
		return a
	else:
		return hcfnaive(b, a % b)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	hcf = a[0]
	for j in range(m):
		hcf = hcfnaive(hcf, a[j])
	if hcf <= n:
		print(n - hcf)
	else:
		b = []
		c = 0
		for j in range(1, int(math.sqrt(hcf)) + 2):
			if hcf % j == 0:
				b.append(j)
				b.append(hcf // j)
				c = c + 2
		b.sort()
		h = 1
		for j in range(c - 1, -1, -1):
			if b[j] <= n:
				h = b[j]
				break
		print(n - h)


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

def fgcd(a):
	r = a[0]
	for i in range(1, len(a)):
		r = gcd(a[i], r)
		if r == 1:
			return 1
	return r
t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	mn = fgcd(a)
	c = 0
	if n >= mn:
		c = n - mn
		print(c)
		continue
	while n > 1:
		if mn % n != 0:
			c += 1
			n -= 1
		else:
			break
	print(c)


import math
for k in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	if m > 1:
		g = math.gcd(l[0], l[1])
		for i in range(2, m):
			g = math.gcd(g, l[i])
	else:
		g = l[0]
	if g == 1:
		print(n - 1)
	elif g < n != 0:
		print(n - g)
	else:
		x = n
		while g % x != 0:
			x -= 1
		print(n - x)


from math import gcd

def lar(g, n):
	for a in range(n, 0, -1):
		if g % a == 0:
			return a
	return -1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	po = list(map(int, input().split()))
	g = po[0]
	for a in range(1, m):
		g = gcd(g, po[a])
	if n == 1:
		print(0)
		continue
	if g < n:
		print(n - g)
	else:
		l = lar(g, n)
		print(n - l)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for i in range(int(input())):
	(n, m) = map(int, input().split())
	spells = [int(j) for j in input().split()]
	if m == 1:
		ans = spells[0]
	else:
		ans = gcd(spells[0], spells[1])
	for j in range(2, m):
		ans = gcd(ans, spells[j])
	if ans <= n:
		print(n - ans)
	else:
		j = 1
		maxi = 0
		while j * j <= ans:
			if ans % j == 0:
				z = ans // j
				if j <= n and j > maxi:
					maxi = j
				if z <= n and z > maxi:
					maxi = z
			j += 1
		print(n - maxi)


import math as x

def lfact(n, k):
	fact = []
	max = 0
	for j in range(1, int(k ** 0.5) + 1):
		if k % j == 0:
			if j <= n and j > max:
				max = j
			if k // j <= n and k // j > max:
				max = k // j
	return max
t = int(input())
for j in range(t):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		g = 0
		for i in range(m):
			g = x.gcd(arr[i], g)
		if g > n:
			g = lfact(n, g)
			print(n - g)
		elif g == n:
			print(0)
		else:
			print(n - g)


from math import ceil, gcd

def factors(x, n):
	f = []
	k = 0
	for i in range(1, int(x ** 0.5) + 1):
		if x % i == 0:
			f.append(i)
			f.append(x // i)
			i1 = x // i
			if i <= n and i > k:
				k = i
			if i1 <= n and i1 > k:
				k = i1
	return k
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif min(p) == 1:
		print(n - 1)
	elif m == 1:
		k = factors(p[0], n)
		print(n - k)
	else:
		a = gcd(p[0], p[1])
		l = len(p)
		for i in range(2, l):
			a = gcd(a, p[i])
		k = factors(a, n)
		print(n - k)


def prime(k, n):
	while n >= 2:
		if k % n == 0:
			return n
		else:
			n -= 1
	return 1

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

def findGCD(arr, n):
	result = arr[0]
	for i in range(1, n):
		result = gcd(arr[i], result)
		if result == 1:
			return 1
	return result
t = int(input())
while t:
	(n, m) = [int(a) for a in input().split()]
	odd = 0
	even = 0
	p = [int(a) for a in input().split()][:m]
	o = findGCD(p, m)
	if o <= n:
		print(n - o)
	else:
		p = prime(o, n)
		print(n - p)
	t -= 1


from math import gcd
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
T = int(input())
for q in range(T):
	(n, m) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	if 0 == 0:
		curr = n
		hf = arr[0]
		mnm = arr[0]
		for i in arr:
			hf = gcd(hf, i)
			mnm = min(i, mnm)
		if mnm <= n:
			curr = mnm
		f = list(factors(hf))
		f.sort(reverse=True)
		for i in f:
			if i <= curr:
				curr = i
				break
		print(n - i)


import math
import sys
from functools import partial, reduce
SAMPLE_IN = 'sample.in'
SAMPLE_ANS = 'sample.ans'

def read_ints(f) -> list:
	return [int(x) for x in f.readline().split()]

def read_case(f=sys.stdin) -> tuple:
	(n, m) = read_ints(f)
	return (n, m, read_ints(f))

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

def greatest_divisor_less_or_equal_than(n, max_value):
	sqrt = int(math.sqrt(n))
	if max_value >= sqrt:
		min_ = sqrt
		sup = min(n, max_value) + 1
	else:
		min_ = 1
		sup = max_value + 1
	return next((i for i in reversed(range(min_, sup)) if n % i == 0), 1)

def solve(n, m, powers):
	powers_gcd = reduce(gcd, powers)
	g = greatest_divisor_less_or_equal_than(powers_gcd, max_value=n)
	return n - g

def make_submission(fin=sys.stdin, fout=sys.stdout):
	output = partial(print, file=fout)
	n_cases = int(fin.readline())
	for t in range(1, n_cases + 1):
		case = read_case(fin)
		answer = solve(*case)
		output(answer)
import os
if os.getenv('GCJ_LOCAL'):
	with open(SAMPLE_IN) as s:
		make_submission(s)
else:
	make_submission()


from math import gcd
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	spells = list(map(int, input().split()))
	if N == 1:
		print(0)
	else:
		curr_gcd = spells[0]
		for i in range(M - 1):
			curr_gcd = gcd(curr_gcd, spells[i + 1])
			if curr_gcd == 1:
				break
		if curr_gcd <= N:
			print(N - curr_gcd)
		else:
			max_factor = 1
			for i in range(2, int((curr_gcd + 1) ** 0.5) + 1):
				if curr_gcd % i == 0:
					if i > N:
						break
					max_factor = i
					if curr_gcd // i <= N:
						max_factor = curr_gcd // i
						break
			print(N - max_factor)


import math
for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))

	def hcf(x, y):
		if x % y == 0:
			return y
		else:
			return hcf(y, x % y)
	ans = a[0]
	for i in range(1, m):
		if a[i] > ans:
			ans = hcf(a[i], ans)
		else:
			ans = hcf(ans, a[i])
	ans1 = 0
	for i in range(1, int(math.sqrt(ans)) + 1):
		if ans % i == 0:
			if i <= n:
				ans1 = max(ans1, i)
			if ans // i <= n:
				ans1 = max(ans1, ans // i)
	print(n - ans1)


import math

def gcdiv(l):
	l.sort()
	ans = math.gcd(l[0], l[1])
	i = 2
	while ans != 1 and i < len(l):
		ans = math.gcd(ans, l[i])
		i = i + 1
	return ans

def lf(gc, n):
	if gc < n:
		return gc
	out = n
	while out > 1:
		if gc % out == 0:
			return out
		out -= 1
	return out
t = int(input())
while t > 0:
	t -= 1
	(n, m) = list(map(int, input().split()))
	l1 = list([int(i) for i in input().split()])
	if len(l1) > 1:
		gc = gcdiv(l1)
	else:
		gc = l1[0]
	print(n - lf(gc, n))


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

def maxfact(x, n):
	lar_fac = 0
	for i in range(1, x + 1):
		if x % i == 0:
			if i <= n:
				lar_fac = max(lar_fac, i)
			elif x / i <= n:
				lar_fac = max(lar_fac, x / i)
	return lar_fac
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	gcd = 0
	for i in range(m):
		gcd = find_gcd(gcd, p[i])
	if gcd > n:
		temp = maxfact(gcd, n)
		gcd = temp
	ans = n - gcd
	print(ans)


import functools

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	ans = functools.reduce(lambda x, y: gcd(x, y), p)
	if ans <= n:
		print(n - ans)
	else:
		f = [1]
		for k in range(ans // 2, 1, -1):
			if ans % k == 0:
				if k <= n:
					f.append(k)
				if ans // k <= n:
					f.append(ans // k)
		res = n - max(f)
		print(res)


import sys
import os
import math
import copy
import random
from bisect import bisect
from io import BytesIO, IOBase
from math import sqrt, floor, factorial, gcd, log, ceil
from collections import deque, Counter, defaultdict
from itertools import permutations, combinations, accumulate

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

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

def Lstr():
	return list(sys.stdin.readline().strip())

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

def Mstr():
	return map(str, sys.stdin.readline().strip().split())

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

def Hash():
	return dict()

def Mod():
	return 1000000007

def Mat2x2(n):
	return [List() for _ in range(n)]

def Lcm(x, y):
	return x * y // gcd(x, y)

def dtob(n):
	return bin(n).replace('0b', '')

def btod(n):
	return int(n, 2)

def watch(x):
	return print(x)

def common(l1, l2):
	return set(l1).intersection(l2)

def Most_frequent(list):
	return max(set(list), key=list.count)

def maxfact(gcd, n):
	facy = 0
	for i in range(1, gcd + 1):
		if gcd % i == 0:
			if i <= n:
				facy = i
			else:
				break
	return facy
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	power = list(map(int, input().split()))
	gcd = power[0]
	for i in range(1, m):
		gcd = math.gcd(gcd, power[i])
	largest_factor = gcd
	if gcd > n:
		largest_factor = maxfact(gcd, n)
	print(n - largest_factor)


def _gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def __gcd(mp):
	if len(mp) == 1:
		return mp[0]
	gcd = _gcd(mp[0], mp[1])
	for i in range(2, len(mp)):
		gcd = _gcd(gcd, mp[i])
	return gcd

def factors(hcf):
	if hcf == 0:
		return [1]
	factor_list = []
	for i in range(1, int(hcf ** 0.5) + 1):
		if hcf % i == 0:
			factor_list.append(i)
			factor_list.append(hcf // i)
	return factor_list
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mp = list(map(int, input().split()))
	hcf = 0
	if m == 1:
		hcf = mp[0]
	elif m > 1:
		hcf = __gcd(mp)
	ans = 0
	factor_list = factors(hcf)
	factor_list.sort(reverse=True)
	for i in factor_list:
		if i <= n:
			ans = n - i
			break
	print(ans)


def gcdf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
for cases in range(t):
	(n, m) = list(map(int, input().split()))
	spells = list(map(int, input().split()))
	kills = 0
	gcd = spells[0]
	for i in range(1, m):
		gcd = gcdf(gcd, spells[i])
	if n > gcd:
		kills += n - gcd
		n = gcd
	if n < gcd:
		for i in range(n, 0, -1):
			if gcd % i == 0:
				break
			kills += 1
	print(kills)


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	p = list(map(int, input().split(' ')))
	g = p[0]
	for i in range(1, m):
		g = gcd(g, p[i])
	if g > n:
		maxEl = 1
		for i in range(n, 0, -1):
			if g % i == 0:
				maxEl = i
				break
		print(n - maxEl)
	else:
		print(n - g)


from sys import stdin, stdout
input = stdin.readline
import math, bisect

def gcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		g = 0
		for i in range(m):
			g = gcd(g, l[i])
		ans = 0
		for i in range(1, int(math.sqrt(g)) + 1):
			if g % i == 0:
				if i <= n:
					ans = max(ans, i)
				j = g // i
				if j <= n:
					ans = max(ans, j)
		print(n - ans)


def gcd(a1, b1):
	if b1 == 0:
		return a1
	else:
		return gcd(b1, a1 % b1)
a = int(input())
for i in range(a):
	b = list(map(int, str(input()).split(' ')))
	c = list(map(int, str(input()).split(' ')))
	k = c[0]
	Ans = 0
	if b[0] == 1:
		print(0)
	elif b[1] == 1:
		if b[0] > c[0]:
			print(abs(b[0] - c[0]))
		elif b[0] == c[0]:
			print(0)
		else:
			for i2 in range(b[0] - 1):
				if c[0] % b[0] != 0:
					Ans += 1
					b[0] -= 1
				else:
					break
			print(Ans)
	else:
		for i1 in range(b[1]):
			k = gcd(c[i1], k)
		if b[0] > k:
			print(abs(b[0] - k))
		elif b[0] == k:
			print(0)
		else:
			for i3 in range(b[0] - 1):
				if k % b[0] != 0:
					Ans += 1
					b[0] -= 1
				else:
					break
			print(Ans)


from math import gcd

def largest_factor(val, n):
	k = min(n, val)
	while k > 0:
		if val % k == 0:
			return k
		k -= 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		val = li[0]
		for i in range(1, m):
			val = gcd(val, li[i])
		print(n - largest_factor(val, n))


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

def snek2(l):
	n1 = l[0]
	n2 = l[1]
	gcd = snek1(n1, n2)
	for i in range(2, len(l)):
		gcd = snek1(gcd, l[i])
	return gcd

def factors(n):
	if n == 0:
		return 1
	x = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			x.append(i)
			x.append(n // i)
	return x
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	h = 0
	if m > 1:
		h = snek2(p)
	else:
		h = p[0]
	f = factors(h)
	f.sort(reverse=True)
	ans = 0
	for j in f:
		if j <= n:
			ans = n - j
			break
	print(ans)


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

def gcd_arr(l):
	num1 = l[0]
	num2 = l[1]
	gcd = find_gcd(num1, num2)
	for i in range(2, len(l)):
		gcd = find_gcd(gcd, l[i])
	return gcd

def factors(n):
	if n == 0:
		return 1
	x = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			x.append(i)
			x.append(n // i)
	return x
test = int(input())
for _ in range(test):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	gcd_of_array = 0
	if m > 1:
		gcd_of_array = gcd_arr(arr)
	else:
		gcd_of_array = arr[0]
	ans = 0
	factors_of_gcd = factors(gcd_of_array)
	factors_of_gcd.sort(reverse=True)
	for i in range(len(factors_of_gcd)):
		if factors_of_gcd[i] <= n:
			ans = n - factors_of_gcd[i]
			break
	print(ans)


from math import gcd, sqrt
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	g = 0
	for i in l:
		g = gcd(g, i)
	if g < n:
		print(n - g)
		continue
	f = 0
	s = int(sqrt(g))
	for i in range(1, s + 1):
		if g % i == 0:
			if i <= n:
				f = max(f, i)
			if g // i <= n:
				f = max(f, g // i)
	print(n - f)


def largestFactor(x, y):
	while x % y:
		y -= 1
	return y

def gcd(a, b):
	if b > a:
		return gcd(b, a)
	if not b:
		return a
	return gcd(b, a % b)

def getGcd(arr):
	_gcd = arr[0]
	for i in range(1, len(arr)):
		_gcd = gcd(_gcd, arr[i])
	return _gcd

def solve(arr, N):
	if N <= 1:
		return 0
	_gcd = getGcd(arr)
	if _gcd == 1:
		return N - 1
	if _gcd < N:
		return N - _gcd
	if not _gcd % N:
		return 0
	return N - largestFactor(_gcd, N)
T = int(input())
for tc in range(T):
	(N, M) = [int(x) for x in input().strip().split(' ')]
	arr = [int(x) for x in input().strip().split(' ')]
	print(solve(arr, N))


import math

def fun(a):
	gcd = a[0]
	for i in range(1, len(a)):
		gcd = math.gcd(gcd, a[i])
	return gcd
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	gcd = fun(a)
	if gcd > n:
		z = [1, gcd]
		for i in range(2, gcd // 2 + 1):
			if gcd % i == 0:
				z.append(i)
		z = sorted(z, reverse=True)
		for x in z:
			if x <= n:
				break
		print(n - x)
	else:
		print(n - gcd)


from math import sqrt

def greatest_divisor(x, y):
	if y == 0:
		return x
	return greatest_divisor(y, x % y)

def largest_fact(p, n):
	maxfact = 0
	for i in range(1, int(sqrt(p)) + 1):
		if p % i == 0:
			if i <= n:
				maxfact = max(maxfact, i)
			if p // i <= n:
				maxfact = max(maxfact, p // i)
	return maxfact
for i in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()[:m]))
	ans = 0
	for i in p:
		ans = greatest_divisor(ans, i)
	if ans > n:
		ans = largest_fact(ans, n)
	kill = n - ans
	print(kill)


import sys
import bisect as bi
import math
from collections import defaultdict as dd
import queue
import heapq
import itertools
input = sys.stdin.readline
import random
sys.setrecursionlimit(10 ** 7)
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input().strip()

def inin():
	return int(input())
for _ in range(inin()):
	(n, m) = cin()
	l = ain()
	if n == 1:
		print(0)
	else:
		gcd = l[0]
		for i in l:
			gcd = math.gcd(gcd, i)
		if gcd < n:
			print(n - gcd)
		else:
			for i in range(n, 0, -1):
				if gcd % i == 0:
					print(n - i)
					break


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	g = 0
	for i in range(len(lst)):
		g = gcd(g, lst[i])
	if g > n:
		fac = [1]
		for i in range(2, g // 2 + 1):
			if g % i == 0:
				if i <= n:
					fac.append(i)
				else:
					break
		g = fac[-1]
	print(n - g)


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

def list_gcd(l):
	result = l[0]
	for i in range(1, len(l)):
		result = gcd(result, l[i])
	return result
t = int(input())
for q in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	g = list_gcd(p)
	if g > n:
		for i in range(n, 0, -1):
			if g % i == 0:
				print(n - i)
				break
	else:
		print(n - g)


tests = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
while tests > 0:
	(n, m) = list(map(int, input().split()))
	ms = list(map(int, input().split()))
	gc = gcd(ms[0], 0)
	for x in ms:
		gc = gcd(gc, x)
	if n < gc:
		left = n
		num = n
		while num > 0:
			if gc % num == 0:
				left = num
				break
			num -= 1
		print(n - left)
	else:
		print(n - gc)
	tests -= 1


import sys
import time
start_time = time.time()
input = sys.stdin.readline
from collections import defaultdict
from collections import Counter
from itertools import permutations

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	spell = list(map(int, input().split()))
	hcf = 0
	for i in spell:
		hcf = gcd(i, hcf)
	ans = 0
	for i in range(1, hcf + 1):
		if i * i > hcf:
			break
		if hcf % i == 0:
			one = i
			other = hcf // i
			if one <= n:
				ans = max(ans, one)
			if other <= n:
				ans = max(ans, other)
	print(n - ans)
print('Execution time : {0:.9f} seconds'.format(time.time() - start_time), file=sys.stderr)


import math
for _ in range(int(input())):
	(n, x) = tuple(map(int, input().split()))
	l = list(map(int, input().split()))
	g = l[0]
	m = 1
	for i in range(1, x):
		g = math.gcd(g, l[i])
	for i in range(1, int(math.sqrt(g)) + 2):
		if g % i == 0:
			if i <= n:
				m = max(m, i)
			if int(g / i) <= n:
				m = max(m, int(g / i))
	print(n - m)


import math
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	p = 0
	for x in arr:
		p = math.gcd(p, x)
		if p == 1:
			break
	if n >= p:
		print(n - p)
	else:
		m = n
		while p % m:
			m -= 1
		print(n - m)
	t -= 1


import sys, math

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

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

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def greatest_factor(x):
	i = 1
	end = math.sqrt(x)
	f = []
	while i <= end:
		if x % i == 0:
			f.append(i)
			f.append(x // i)
		i += 1
	f.sort(reverse=True)
	return f
for _ in range(int(input())):
	(n, m) = multiple_input()
	a = list_input()
	g = a[0]
	for i in a:
		g = gcd(g, i)
	fact = greatest_factor(g)
	ans = 0
	for i in fact:
		if i <= n:
			ans = n - i
			break
	print(ans)


import math

def maxfactor(x, n):
	i = 1
	f = 1
	while i * i <= x:
		if x % i == 0:
			if i <= n:
				f = max(f, i)
			if x // i <= n:
				f = max(f, x // i)
		i = i + 1
	return f
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	g = 0
	for i in arr:
		g = math.gcd(g, i)
	k = maxfactor(g, n)
	print(n - k)


from math import gcd

def maxfactor(x, n):
	i = 1
	f = 1
	while i * i <= x:
		if x % i == 0:
			if i <= n:
				f = max(f, i)
			if x // i <= n:
				f = max(f, x // i)
		i += 1
	return f
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	g = 0
	for i in p:
		g = gcd(g, i)
	if g > n:
		g = maxfactor(g, n)
	print(n - g)


import math
import functools
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	mi = 0
	g = functools.reduce(lambda x, y: math.gcd(x, y), p)
	ma = 0
	if g > n:
		for i in range(1, int(math.sqrt(g)) + 1):
			if g % i == 0:
				if i <= n:
					ma = max(ma, i)
				if g // i <= n:
					ma = max(ma, g // i)
		print(n - ma)
		continue
	print(n - g)


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

def answer():
	g = p[0]
	for v in p[1:]:
		g = gcd(g, v)
	nk = 1
	for i in range(1, int(g ** 0.5) + 1):
		if g % i == 0:
			if i <= n:
				nk = max(nk, i)
			if g // i <= n:
				nk = max(nk, g // i)
	return n - nk
for T in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	print(answer())


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = get_ints()
	a = get_array()
	g = 0
	for i in range(m):
		g = math.gcd(g, a[i])
	mx_factor = 0
	for i in range(1, int(g ** 0.5) + 1):
		if g % i == 0:
			if i <= n:
				mx_factor = max(mx_factor, i)
			if g // i <= n:
				mx_factor = max(mx_factor, g // i)
	ans = n - mx_factor
	print(ans)


from math import gcd, sqrt, ceil

def fac(x, n):
	mx = 1
	for i in range(1, ceil(sqrt(x)) + 1):
		if x % i == 0:
			if i <= n:
				mx = max(mx, i)
			if x // i <= n:
				mx = max(mx, x // i)
	return mx
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	rev = n
	lis = list(map(int, input().split()))
	g = lis[0]
	for i in lis:
		g = gcd(g, i)
	if n > g:
		k = n - g
	else:
		val = fac(g, n)
		k = n - val
	print(k)


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	a1 = 0
	for i in arr:
		a1 = gcd(a1, i)
	ans = 0
	if a1 > n:
		i = 1
		while i * i <= a1:
			if a1 % i == 0:
				if i <= n:
					ans = max(ans, i)
				if a1 // i <= n:
					ans = max(ans, a1 // i)
			i += 1
		a1 = ans
	print(n - a1)


import sys
input = sys.stdin.readline
from math import ceil, floor, sqrt, gcd, log
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip('\r\n')
for _ in range(ri()):
	(n, m) = rl()
	p = rl()
	if n == 1:
		print(0)
		continue
	ans = p[0]
	for i in range(m):
		ans = gcd(ans, p[i])
	if ans > n:
		f = 0
		i = 1
		while i * i <= ans and i <= n:
			if ans % i == 0:
				if ans // i <= n:
					f = max(f, ans // i)
				else:
					f = max(f, i)
			i += 1
		ans = f
	print(n - ans)


from math import gcd

def factors(n):
	if n == 0:
		return [1]
	x = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			x.append(i)
			x.append(n // i)
	return x
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 1:
		hcf = a[0]
	elif k == 2:
		hcf = gcd(a[0], a[1])
	else:
		x = gcd(a[0], a[1])
		for i in range(2, k):
			x = gcd(x, a[i])
		hcf = x
	fact = factors(hcf)
	fact.sort(reverse=True)
	final = 0
	for i in fact:
		if i <= n:
			final = n - i
			break
	print(final)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	P = list(map(int, input().split()))
	g = ans = 0
	for i in P:
		g = math.gcd(g, i)
	for i in range(1, int(math.sqrt(g)) + 1):
		if g % i == 0:
			if i <= n:
				ans = max(ans, i)
			if g // i <= n:
				ans = max(ans, g // i)
	print(n - ans)


import math

def maxfact(g, n):
	maxfactor = 0
	i = 1
	while i * i <= g:
		if g % i == 0:
			if i <= n:
				maxfactor = max(maxfactor, i)
			if g // i <= n:
				maxfactor = max(maxfactor, g // i)
		i += 1
	return maxfactor

def find_kills(n, m, spells):
	gcd = 0
	for i in range(m):
		gcd = math.gcd(gcd, spells[i])
	if gcd > n:
		lf = maxfact(gcd, n)
		gcd = lf
	return n - gcd
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split(' '))
	spells = list(map(int, input().split(' ')))
	print(find_kills(n, m, spells))


import math
import random

def findGCD(l: list):
	ans = l[0]
	for i in l[1:]:
		ans = math.gcd(ans, i)
	return int(ans)

def cirChaos(N, M, spells: list):
	GCD = findGCD(spells)
	rem = 0
	if GCD > N:
		i = N
		while i > 0:
			if GCD % i == 0:
				rem = i
				break
			i -= 1
	else:
		rem = GCD
	return N - rem
T = int(input())
for t in range(T):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	spells = input().split()
	spells = list(map(int, spells))
	print(cirChaos(N, M, spells))


import math

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

def maxfact(g, n):
	i = 1
	maxf = None
	while i * i <= g:
		if g % i == 0:
			if i <= n:
				maxf = i
			if math.floor(g / i) <= n:
				maxf = math.floor(g / i)
				break
		i = i + 1
	return maxf
t = int(input())
while t > 0:
	t = t - 1
	[n, m] = [int(x) for x in input().split(' ')]
	spells = [int(x) for x in input().split(' ')]
	g = spells[0]
	for i in range(1, m):
		g = gcd(g, spells[i])
	print(n - maxfact(g, n))


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

def hf(n, g):
	d = min(g, n)
	for i in range(d, -1, -1):
		if g % i == 0:
			return i
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, m):
		g = gcd(g, l[i])
	f = hf(n, g)
	print(n - f)


import math
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	g = 0
	for i in range(m):
		g = math.gcd(g, l[i])
	if n - g > 0:
		print(n - g)
	else:
		t = n
		while g % n != 0:
			n -= 1
		print(t - n)


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	if len(l) == 1:
		gcd = l[0]
	elif len(l) == 2:
		num1 = l[0]
		num2 = l[1]
		gcd = find_gcd(num1, num2)
	else:
		num1 = l[0]
		num2 = l[1]
		gcd = find_gcd(num1, num2)
		for i in range(2, len(l)):
			gcd = find_gcd(gcd, l[i])
	pr = 1
	factors = []
	while pr * pr <= gcd:
		if gcd % pr == 0:
			factors.append(pr)
			factors.append(gcd // pr)
			pr += 1
		else:
			pr += 1
	factors.sort()
	factors.reverse()
	for i in factors:
		if i <= n:
			print(n - i)
			break


import math

def factor(n):
	if n == 0:
		return 1
	facts = []
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			facts.append(i)
			facts.append(n // i)
	return facts

def solve(n, m):
	if n == 1:
		return 0
	if m == 1:
		gcd_ = powers[0]
	else:
		gcd_ = math.gcd(powers[0], powers[1])
		for i in range(2, m):
			gcd_ = math.gcd(gcd_, powers[i])
	factors = factor(gcd_)
	factors.sort(reverse=True)
	ans = 0
	for i in factors:
		if i <= n:
			ans = n - i
			break
	return ans
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	powers = list(map(int, input().split()))
	ans = solve(n, m)
	print(ans)


import math

def factors(n):
	i = 1
	while i * i < n:
		if n % i == 0:
			yield i
		i += 1
	for i in range(int(math.sqrt(n)), 0, -1):
		if n % i == 0:
			yield (n // i)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	g = None
	if len(p) == 1:
		g = p[0]
	g = p[0]
	for w in p[1:]:
		g = math.gcd(g, w)
	k = 1
	if g < n:
		k = g
	else:
		ff = list(factors(g))
		ff.sort()
		for f in ff:
			if f > n:
				break
			else:
				k = f
		if n == 1:
			print(0)
			continue
	print(n - k)


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

def printAllDivisors(arr, m, n):
	g = arr[0]
	divisors = dict()
	for i in range(1, m):
		g = gcd(arr[i], g)
	for i in range(1, g + 1):
		if i * i > g:
			break
		if g % i == 0:
			divisors[i] = 1
			if g // i != i:
				divisors[g // i] = 1
	maxx = 0
	for it in sorted(divisors):
		if it <= n:
			maxx = it
	return maxx
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	print(n - printAllDivisors(arr, m, n))


def GCD(x, y):
	if not y:
		return x
	return GCD(y, x % y)

def gcd(arr):
	temp1 = arr[0]
	for i in range(1, len(arr)):
		temp1 = GCD(temp1, arr[i])
	return temp1

def hcf(gcd, N):
	if gcd <= N:
		return gcd
	else:
		for i in range(gcd // 2, 0, -1):
			if gcd % i == 0 and i <= N:
				return i
for t in range(int(input())):
	(N, M) = map(int, input().split())
	po = list(map(int, input().split()))
	gc = gcd(po)
	print(N - hcf(gc, N))


def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	list_m = list(map(int, input().split()))
	if N == 1:
		print(0)
	elif len(list_m) == 1:
		gcd_val = list_m[0]
		N_tmp = N
		if gcd_val >= N:
			while gcd_val > 0:
				if gcd_val % N_tmp == 0:
					print(N - N_tmp)
					break
				else:
					N_tmp -= 1
		else:
			print(N - gcd_val)
	else:
		gcd_val = list_m[0]
		for x_m in list_m[1:]:
			gcd_val = GCD(gcd_val, x_m)
		N_tmp = N
		if gcd_val >= N:
			while gcd_val > 0:
				if gcd_val % N_tmp == 0:
					print(N - N_tmp)
					break
				else:
					N_tmp -= 1
		else:
			print(N - gcd_val)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		g = 0
		for i in range(m):
			g = math.gcd(g, a[i])
		if n > g:
			print(n - g)
		elif g == 1:
			print(n - 1)
		else:
			temp = n
			ans = 0
			while g % temp != 0:
				temp -= 1
			print(n - temp)