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$.

Difficulty: interview

Starter code:

Solutions:
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 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)
     break
    if ans//k <= n:
     f.append(ans//k)
  res = n-max(f)
  print(res)

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)

# cook your dish here
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)

# cook your dish here
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))


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

# cook your dish here
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)


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 = list(map(int, input().split()))
 a = list(map(int, input().split()))
 a.sort()
 # mn = min(a)
 mn = fgcd(a)
 # print(mn)
 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)


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 = list(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))



# cook your dish here
import math 

def gcd(a,b):
 if b == 0:
  return a
 return gcd(b,a%b)
 
for _ in range(int(input())):
 n,m=list(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(2,int(math.sqrt(g)+1)):
   if g%i == 0:
    if i<=n:
     maxEl = max(maxEl,i)
    if g//i<=n:
     maxEl = max(maxEl,g//i)
  print(n - maxEl) 
 else:
  print(n - g)
 


# cook your dish here
import math 

def gcd(a,b):
 if b == 0:
  return a
 return gcd(b,a%b)
 
for _ in range(int(input())):
 n,m=list(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(2,int(math.sqrt(g)+1)):
   if g%i == 0:
    if i<=n:
     maxEl = max(maxEl,i)
    if g//i<=n:
     maxEl = max(maxEl,g//i)
  print(n - maxEl) 
 else:
  print(n - g)
 


# cook your dish here
import math 

def gcd(a,b):
 if b == 0:
  return a
 return gcd(b,a%b)
 
for _ in range(int(input())):
 n,m=list(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 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)

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)
  


# cook your dish here
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)
 
 
 
 
 


# cook your dish here# cook your dish here
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))
 
  
 
 
 
 
 
 
 


# cook your dish here
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)
 else:
  if 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)

# cook your dish here
try:
 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):
  #print(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)
except:
 pass

# cook your dish here
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):
 #print(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)