Luigi has an array A of N positive integers. He wants to make all elements of the array equal. 

In one move, he can:
Choose an index i (1≤ i ≤ N) and divide the element A_{i} by any one of its [divisors].  
In other words, he can choose a positive integer X such that X | A_{i} and set A_{i} := \frac{A_{i}}{X}.

Find the minimum number of moves required to make all the elements of the array equal.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains N, the size of array A.
- The second line of each test case contains N space-separated integers, the elements of array A.

------ Output Format ------ 

For each test case, output on a new line, the minimum number of moves required to make all elements of the array equal.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 3000$
$1 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2
11 22
5
38 38 38 38 38
4
4 4 16 8
4
11 13 17 19

----- Sample Output 1 ------ 
1
0
2
4

----- explanation 1 ------ 
Test case $1$: We can change $22$ to $11$ using an operation (divide by $2$). Thus, using one operation, we made all the elements equal.

Test case $2$: All numbers are already same. Thus, we do not need to do any operations.

Test case $3$: We make the following operations:
- Choose $i = 3$ and $X = 4$, such that $4|16$. Thus, $A_{3} := \frac{16}{4} = 4$.
- Choose $i = 4$ and $X = 2$, such that $2|8$. Thus, $A_{4} := \frac{8}{2} = 4$.

Thus, using two operations, we made all the elements equal.

Test case $4$: We make the following operations:
- Choose $i = 1$ and $X = 11$, such that $11|11$. Thus, $A_{1} := \frac{11}{11} = 1$.
- Choose $i = 2$ and $X = 13$, such that $13|13$. Thus, $A_{2} := \frac{13}{13} = 1$.
- Choose $i = 3$ and $X = 17$, such that $17|17$. Thus, $A_{3} := \frac{17}{17} = 1$.
- Choose $i = 4$ and $X = 19$, such that $19|19$. Thus, $A_{4} := \frac{19}{19} = 1$.

Thus, using four operations, we made all the elements equal.

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
import math
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	gcd = 0
	for i in array:
		gcd = math.gcd(gcd, i)
	for i in array:
		if i == gcd:
			n -= 1
	print(n)


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = list(map(int, input().split()))
	death = max(life)
	for i in life:
		if death > i:
			death = i
	(final, total) = (0, 0)
	for j in life:
		if j != death:
			if j % death == 0:
				final += 1
			else:
				total = 1
				break
	if total:
		print(wife)
	else:
		print(final)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = list(set(l))
	ans = []
	ans.append(n)
	for k in s:
		d = 1
		f = n
		for j in l:
			if j % k != 0:
				d = 0
				break
			if j == k:
				f -= 1
		if d:
			ans.append(f)
	print(min(ans))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = min(a)
	c = 0
	for i in range(n):
		if a[i] % b == 0:
			c += 1
	if c == n:
		print(n - a.count(b))
	else:
		print(n)


import math
T = int(input())
for t in range(T):
	a = int(input())
	b = list(map(int, input().split()))
	count = 0
	gcd = 0
	for i in b:
		gcd = math.gcd(gcd, i)
	for i in b:
		if i != gcd:
			count += 1
	print(count)


from math import gcd
from functools import reduce
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	GCD = reduce(gcd, lst)
	ans = 0
	for x in lst:
		ans += x // GCD > 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	l = len(a)
	c = a.count(m)
	if c == len(a):
		print(0)
	else:
		a = list(filter(m.__ne__, a))
		for i in a:
			if i % m != 0:
				print(l)
				break
		else:
			print(len(a))


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = 0
	c = 0
	for i in l:
		g = math.gcd(i, g)
	for i in l:
		if i != g:
			c = c + 1
	print(c)


from math import gcd
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 1
	r = min(a)
	for i in a:
		if i % r != 0:
			flag = 0
			print(n)
			break
	if flag == 1:
		print(n - a.count(r))


from math import gcd
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for i in range(1, n):
		g = gcd(g, a[i])
	print(n - a.count(g))


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	a = min(A)
	b = 0
	for i in A:
		if i % a != 0:
			b = 1
			break
	if b == 1:
		print(N)
	else:
		print(N - A.count(a))


t = int(input())
for tc in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	x = 0
	m = min(a)
	for k in a:
		if k % m == 0 and k != m:
			x += 1
		if k % m != 0 and k != m:
			x = len(a)
			break
	print(x)


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	a = min(A)
	c = 0
	for i in A:
		if i % a != 0:
			c = 1
			break
	if c == 1:
		print(n)
	else:
		print(n - A.count(a))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = min(a)
	ans = 0
	for i in a:
		if i % x == 0 and i != x:
			ans = ans + 1
		if i % x != 0:
			ans = len(a)
			break
	print(ans)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	m = min(l)
	cont = 0
	for j in l:
		if j % m != 0:
			cont = len(l)
			break
		if j % m == 0 and j != m:
			cont = cont + 1
	print(cont)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = min(x)
	count = 0
	for z in x:
		if z % y != 0:
			count = 1
			break
	if count == 1:
		print(n)
	else:
		print(n - x.count(y))


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	gcd = arr[0]
	for j in arr:
		gcd = math.gcd(gcd, j)
	ans = 0
	arr.sort()
	for j in range(length):
		if arr[j] != gcd:
			ans += 1
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	list = [int(i) for i in input().split()]
	gc = 0
	count = 0
	for i in list:
		gc = math.gcd(i, gc)
	for i in list:
		if i != gc:
			count += 1
	print(count)


k = int(input())
for i in range(k):
	n = int(input())
	lis = list(map(int, input().split()))
	chota = min(lis)
	c = 0
	for i in lis:
		if i % chota != 0:
			print(n)
			c = 1
			break
	if c == 0:
		print(n - lis.count(chota))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	x = min(lst)
	flag = 0
	for i in lst:
		if i % x != 0:
			print(n)
			flag = 1
			break
	if flag == 0:
		print(n - lst.count(x))


def same(ls):
	for i in range(len(lst)):
		ls[i] = ls[i] == ls[-1]
	return all(ls)

def make(x, lst):
	for i in range(len(lst)):
		lst[i] = lst[i] % x
	return lst.count(0)
T = int(input())
for _ in range(T):
	N = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	ls1 = lst.copy()
	if same(ls1):
		print(0)
	else:
		x = lst[0]
		y = [i % x != 0 for i in lst]
		if any(y):
			print(len(lst))
		else:
			ls2 = lst.copy()
			while ls2[0] == x:
				ls2.remove(x)
			print(make(x, ls2))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	m = 0
	flag = 0
	l.sort()
	for i in range(len(l) - 1):
		if l[i] != l[i + 1]:
			flag = 1
			break
	if flag == 0:
		print(0)
	else:
		for i in range(1, n):
			if l[i] % l[0] == 0 and l[i] != l[0]:
				c += 1
			elif l[i] % l[0] != 0:
				m = n
				break
		if m == n:
			print(n)
		else:
			print(c)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	m = max(A)
	count = 0
	s = 0
	for i in A:
		if m > i:
			m = i
	for j in A:
		if j != m:
			if j % m == 0:
				count += 1
			else:
				s = 1
				break
	if s:
		print(n)
	else:
		print(count)


import math

def big_gcd(arr):
	b = arr.copy()
	c = math.gcd(b[-1], b[-2])
	b.pop()
	b.pop()
	while len(b) > 0:
		c = math.gcd(c, b[-1])
		b.pop()
	return c
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		print(0)
		continue
	g = big_gcd(a)
	ans = 0
	for i in a:
		ans += int(not g == i)
	print(ans)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	x = a[0]
	for i in range(n):
		x = math.gcd(x, a[i])
	for i in range(n):
		if a[i] != x:
			a[i] = a[i] / x
			count += 1
		else:
			pass
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	val = a[0]
	for i in range(1, n):
		val = math.gcd(val, a[i])
	res = 0
	for num in a:
		if num != val:
			res += 1
	print(res)


from math import gcd
from functools import reduce
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	G = reduce(gcd, A)
	B = [a > G for a in A]
	print(sum(B))


def GCD(a, b):
	if b == 0:
		return abs(a)
	else:
		return GCD(b, a % b)
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	g = arr[0]
	for x in arr:
		g = GCD(x, g)
	print(n - arr.count(g))
	t -= 1


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	m = min(l)
	c = 0
	for i in l:
		if i % m == 0:
			c += 1
	if len(s) > 1:
		if c == len(l):
			print(len(l) - l.count(m))
		else:
			print(len(l))
	else:
		print(0)


import sys
for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in sys.stdin.readline().split()]
	x = min(arr)
	flag = False
	ans = 0
	for i in range(len(arr)):
		if arr[i] % x != 0:
			flag = True
			break
		elif arr[i] != x:
			ans += 1
	if flag == True:
		print(len(arr))
	else:
		print(ans)
		print()


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	minA = min(A)
	count = 0
	for a in A:
		if a % minA != 0:
			count = N
			break
		elif a // minA > 1:
			count += 1
	print(count)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	x = min(l)
	c = 0
	for i in l:
		if i % x != 0:
			c = n
			break
		elif i // x > 1:
			c += 1
	print(c)
	t -= 1


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	low = min(arr)
	for i in arr:
		low = gcd(low, i)
		if low == 1:
			break
	count = 0
	for i in arr:
		if i != low:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	v.sort()
	a = 0
	b = v[0]
	for i in v:
		if b == i:
			continue
		if i % b != 0:
			a = n
			break
		a += 1
	print(a)


for i in range(int(input())):
	y = int(input())
	z = list(map(int, input().split()))
	x = set(z)
	if len(x) == 1:
		print(0)
	else:
		z.sort()
		c = 0
		for i in range(y):
			if i >= 1 and z[i] != z[0]:
				if z[i] % z[0] == 0:
					c += 1
				else:
					c = len(z)
					break
		print(c)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	ans = l[0]
	for i in range(1, n):
		ans = math.gcd(ans, l[i])
	print(n - l.count(ans))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = min(a)
	flag = 0
	count = 0
	for i in a:
		if i % s == 0:
			if i != s:
				count += 1
		else:
			flag = 1
			break
	if flag == 0:
		print(count)
	else:
		print(n)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = min(a)
	f = 1
	c = 0
	for i in a:
		if i != m:
			if i % m == 0:
				c += 1
			else:
				f = 0
				break
	if f == 1:
		print(c)
	else:
		print(n)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	maxi = min(l)
	c = 0
	flag = 0
	for j in l:
		if j != maxi:
			if j % maxi == 0:
				c += 1
			else:
				flag = 1
				break
	if flag == 0:
		print(c)
	else:
		print(n)


import math
for j in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	i = 1
	h = l[i - 1]
	for k in range(1, n):
		h = math.gcd(h, l[k])
	for k in range(n):
		if l[k] == h:
			pass
		else:
			count = count + 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	mini = min(a)
	count = 0
	for i in a:
		if i % mini == 0:
			count += 1
	if len(s) > 1:
		if count == len(a):
			print(len(a) - a.count(mini))
		else:
			print(len(a))
	else:
		print(0)


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = 0
	g = 0
	for i in range(n):
		g = math.gcd(g, a[i])
	for i in range(n):
		if a[i] != g:
			h += 1
	print(h)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in l:
		g = gcd(g, i)
	c = 0
	for i in l:
		if i != g:
			c += 1
	print(c)


from math import gcd
from functools import reduce
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	g = reduce(gcd, a)
	print(n - a.count(g))


x = int(input())
for i in range(x):
	y = int(input())
	z = input().split()
	z = list(map(int, z))
	counter = 0
	n = min(z)
	for m in range(len(z)):
		if z[m] % n == 0 and z[m] != n:
			counter += 1
		if z[m] % n != 0:
			counter = len(z)
			break
	print(counter)


from math import gcd
from functools import reduce
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = reduce(lambda a, b: gcd(a, b), l)
	print(len(l) - l.count(k))


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		c = l[0]
		for i in l[1:]:
			c = gcd(c, i)
		a = 0
		for i in l:
			if i != c:
				a += 1
		print(a)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		gc = l[0]
		for i in l[1:]:
			gc = gcd(gc, i)
		cnt = 0
		for i in l:
			if i != gc:
				cnt += 1
		print(cnt)


lster = lambda : list(map(int, input().split()))

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

def sol():
	n = int(input())
	l = lster()
	if n == 1:
		print(0)
	else:
		gc = l[0]
		for i in l[1:]:
			gc = gcd(gc, i)
		cnt = 0
		for i in l:
			if i != gc:
				cnt += 1
		print(cnt)
for _ in range(int(input())):
	sol()


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

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

def invr():
	return map(int, input().split())

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
from math import gcd
from functools import reduce
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	g = reduce(gcd, A)
	ans.append(N - A.count(g))
outplt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

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

def invr():
	return map(int, input().split())

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	mn = min(A)
	for a in A:
		if a % mn:
			ans.append(N)
			break
	else:
		ans.append(N - A.count(mn))
outplt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

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

def invr():
	return map(int, input().split())

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))

def gcd(x, y):
	return gcd(y, x % y) if x % y else y
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	g = A[0]
	for a in A[1:]:
		g = gcd(a, g)
	ans.append(N - A.count(g))
outplt(ans)


from math import gcd
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	x = 0
	m = min(l)
	for i in l:
		if i % m == 0:
			x = x + 1
		else:
			break
	if x != n:
		print(n)
	else:
		print(n - l.count(m))


t = int(input())
for i in range(t):
	num_elems = int(input())
	elems_list = list(map(int, input().split()))
	mini = min(elems_list)
	x = 0
	for i in range(num_elems):
		if elems_list[i] % mini == 0:
			x += 1
		else:
			break
	if x != num_elems:
		print(num_elems)
	else:
		print(f'{num_elems - elems_list.count(mini)}')


t = eval(input(''))
while t != 0:
	t -= 1
	n = eval(input(''))
	a = []
	g = 0
	k = 0
	a = list(map(int, input().split()))
	h = min(a)
	for i in range(n):
		if a[i] > h:
			d = a[i] // h
			if h == a[i] / d:
				g += 1
			else:
				k = 1
	if k == 1:
		print(n)
	else:
		print(g)