You are given an array A_{1}, A_{2}, \dots, A_{N} consisting of N integers. Your goal is to make the GCD of all the elements in the array an odd integer. To achieve this goal, you can do the following operation any number of times:

Choose an index i\;(1≤ i ≤ N) such that A_{i} > 1 and set A_{i} = \lfloor \frac{A_{i}}{2}\ \rfloor

You can choose an index multiple times during the operations. Find the minimum number of operations after which GCD of all the elements in the array becomes an odd integer.

Note: \lfloor x \rfloor : Returns the largest integer that is less than or equal to x (i.e  rounds down to the nearest integer). For example, \lfloor 1.5 \rfloor = 1, \lfloor 2 \rfloor = 2, \lfloor \frac{7}{2}\ \rfloor \;= \lfloor 3.5 \rfloor \;= 3.

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

- 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 a single integer N.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, print a single line containing one integer - the minimum number of operations after which GCD of all the elements in the array becomes an odd integer.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed  $5\cdot10^{5}$

----- Sample Input 1 ------ 
3
3
2 3 5
2
4 6
3 
4 12 24
----- Sample Output 1 ------ 
0
1 
2
----- explanation 1 ------ 
Test case $1$: The GCD of all integers in the array is already $1$, which is odd.

Test case $2$: You choose the index $i = 2$ and set $A_{2} = \lfloor \frac{6}{2}\ \rfloor = \lfloor 3 \rfloor = 3$. So the array becomes $[4, 3]$ and the GCD of $4$ and $3$ is $1$.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = float('inf')
	for i in a:
		v = 0
		while i & 1 == 0:
			i //= 2
			v += 1
		ans = min(ans, v)
		if v == 0:
			break
	print(ans)


import sys
tc = int(input().strip())
for t in range(tc):
	n = int(input().strip())
	arr = list(map(int, input().split()))
	operations = sys.maxsize
	for i in arr:
		if i % 2 == 1:
			operations = 0
			break
		else:
			temp = 0
			while i % 2 != 1:
				i = i // 2
				temp += 1
			operations = min(temp, operations)
	print(operations)


def find(g):
	u = 0
	while g > 1:
		if g % 2 == 1:
			return u
		else:
			g = g // 2
			u += 1
	return u
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	r = 1100000000000001
	for i in range(n):
		if find(a[i]) < r:
			r = find(a[i])
	print(r)


T = int(input())
while T > 0:
	n = int(input())
	ls = list(map(int, input().split()))
	maxo = 100000000
	for i in range(len(ls)):
		if ls[i] % 2 == 1:
			maxo = 0
		else:
			count = 0
			while ls[i] % 2 == 0:
				count += 1
				ls[i] = ls[i] / 2
			maxo = min(count, maxo)
	print(maxo)
	T = T - 1


from math import ceil
t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	count = 0
	while s == 0:
		for i in range(n):
			if a[i] % 2 == 1:
				s = 1
				break
			else:
				a[i] = ceil(a[i] / 2)
		count += 1
	print(count - 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		if i % 2 != 0:
			ans = 1
	if ans == 0:
		res = 1000000000.0
		for i in range(len(l)):
			ans = 0
			while l[i] % 2 != 1:
				l[i] /= 2
				ans += 1
			if ans < res:
				res = ans
		print(res)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = []
	for j in l:
		count = 0
		while j % 2 == 0:
			j = j / 2
			count = count + 1
		m.append(count)
	print(min(m))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	T = []
	for i in A:
		t = i
		op = 0
		while t % 2 == 0:
			t = t // 2
			op += 1
		T.append(op)
	print(min(T))


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = int(1000000000.0)
	for el in arr:
		x = 0
		while el % 2 == 0:
			el = el // 2
			x += 1
		ans = min(ans, x)
	print(ans)
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mi = 9999999
	p = 0
	for i in l:
		if i % 2 != 0:
			print(0)
			p = 1
			break
		else:
			c = 0
			k = i
			while k % 2 == 0:
				k = k // 2
				c += 1
			if c < mi:
				mi = c
	if p == 0:
		print(mi)


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	e = []
	o = []
	for k in A:
		if k % 2 == 0:
			e.append(k)
		else:
			o.append(k)
	if o != []:
		print(0)
	else:
		c = 0
		ANS = n
		for k in range(n):
			s = e[k]
			c = 0
			while s % 2 != 1:
				s //= 2
				c += 1
			ANS = min(ANS, c)
		print(ANS)


def check_for_odds(arr):
	ans = 100
	for i in range(len(arr)):
		if arr[i] % 2 == 1:
			ans = 0
			break
	return ans

def divide_by_2(arr):
	for i in range(len(arr)):
		arr[i] = arr[i] / 2
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	counter = 0
	while check_for_odds(arr) != 0:
		divide_by_2(arr)
		counter = counter + 1
	print(counter)


def oddGCD(arr):
	for i in range(len(arr)):
		count = 0
		temp = arr[i]
		while temp % 2 == 0:
			temp /= 2
			count += 1
		if i == 0 or count < ans:
			ans = count
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(oddGCD(arr))


def make_odd(n):
	c = 0
	while n & 1 != 1:
		c = c + 1
		n = n >> 1
	return c
for l in range(int(input())):
	input()
	arr = [int(a) for a in input().split()]
	op = float('inf')
	for l in arr:
		op = min(op, make_odd(l))
	print(op)


from math import gcd

def make_odd(n):
	c = 0
	while n & 1 != 1:
		c = c + 1
		n = n >> 1
	return c
for l in range(int(input())):
	input()
	arr = [int(a) for a in input().split()]
	g = arr[0]
	for i in range(1, len(arr)):
		g = gcd(g, arr[i])
	if g & 1 == 1:
		print(0)
	else:
		op = float('inf')
		for l in arr:
			op = min(op, make_odd(l))
		print(op)


t = int(input())
while t:
	n = int(input())
	ls = [int(i) for i in input().split(' ')]
	mCount = 10 ** 9
	odd = 0
	for i in range(n):
		if ls[i] & 1:
			odd += 1
	if odd == 0:
		for i in range(n):
			count = 0
			if ls[i] % 2 == 0:
				while ls[i] % 2 == 0:
					count += 1
					ls[i] //= 2
				mCount = min(mCount, count)
		print(mCount)
	else:
		print(0)
	t -= 1


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = l[0]
	ct = 0
	for i in range(1, len(l)):
		t = gcd(t, l[i])
	if t % 2 != 0:
		print(0)
	else:
		while t != 1:
			t = t // 2
			ct += 1
		print(ct)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	c = 99999999999
	for i in lst:
		t = 0
		while i % 2 == 0:
			i = i // 2
			t += 1
		c = min(c, t)
	print(c)


import math

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	n1 = l[0]
	n2 = l[1]
	g = gcd(n1, n2)
	for i in range(2, len(l)):
		g = gcd(g, l[i])
	r = math.log(g, 2)
	print(int(r))


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in l[1:]:
		g = gcd(g, i)
	c = 0
	while g // 2 ** c % 2 == 0:
		c += 1
	print(c)


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	step = []
	for i in a:
		ct = 0
		while i % 2 == 0:
			ct += 1
			i //= 2
		step.append(ct)
	ans = min(step)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	for i in range(len(l)):
		c = 0
		t = l[i]
		while t % 2 == 0:
			t = t // 2
			c += 1
		if a > c or i == 0:
			a = c
	print(a)


def number2(a):
	result = 0
	while a % 2 == 0:
		result += 1
		a //= 2
	return result
for i in range(int(input())):
	n = int(input())
	res = 32
	listx = list(map(int, input().split()))
	for i in range(n):
		prov = number2(listx[i])
		if prov < res:
			res = prov
	print(res)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	a = arr[0]
	for i in range(1, n):
		b = arr[i]
		a = gcd(a, b)
	c = 0
	while a % 2 == 0:
		a = a / 2
		c += 1
	print(c)
	t -= 1


from math import gcd

def help(n):
	c = 0
	while n % 2 == 0:
		n = n // 2
		c += 1
	return c

def pro(arr):
	n = len(arr)
	x = arr[0]
	ans = help(arr[0])
	for i in range(1, n):
		x = gcd(x, arr[i])
		ans = min(ans, help(arr[i]))
	print(ans)
n = int(input())
for i in range(n):
	n = int(input())
	arr = list(map(int, input().split()))
	pro(arr)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	odd_count = 0
	for i in arr:
		if i % 2 != 0:
			odd_count += 1
	if odd_count > 0:
		print(0)
	else:
		ans = 0
		odd_count = 0
		flag = True
		while flag:
			odd_count += 1
			for i in range(n):
				arr[i] = arr[i] // 2
				if arr[i] % 2 != 0:
					print(odd_count)
					flag = False
					break


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	op = 0
	while count == 0:
		for i in range(n):
			if a[i] % 2 != 0:
				count += 1
				break
		else:
			op += 1
			for i in range(n):
				a[i] = int(a[i] / 2)
	print(op)


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

def checkmin(l):
	m = []
	for i in l:
		cnt = 0
		while i % 2 == 0:
			i //= 2
			cnt += 1
		m.append(cnt)
	return min(m)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = l[0]
	for i in range(1, n):
		ans = gcd(l[i], ans)
	if ans & 1 == 1:
		print(0)
	else:
		print(checkmin(l))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ll = []
	for i in l:
		if i % 2 != 0:
			ll.append(0)
		if i % 2 == 0:
			c = 0
			while i % 2 == 0:
				i = i // 2
				c += 1
			ll.append(c)
	print(min(ll))


T = int(input())
j = 0
while j < T:
	N = int(input())
	temp = input().split()
	times = None
	for i in range(N):
		num = int(temp[i])
		t = 0
		while True:
			if num % 2 == 1:
				break
			else:
				num = num // 2
				t += 1
		if times is None:
			times = t
		elif t < times:
			times = t
	print(times)
	j += 1


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20

def op(x):
	y = x
	a = 0
	while y % 2 == 0:
		y //= 2
		a += 1
	return a
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = +inf
	for i in range(n):
		cur_element = l[i]
		ans = min(ans, op(cur_element))
	print(ans)


def fun(x):
	c = 0
	if x == 2:
		return 1
	while x % 2 == 0 and x > 0:
		x = x // 2
		c += 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	m = 10000000000
	b = 0
	d = 0
	for x in a:
		if x % 2 == 0:
			d = fun(x)
			if d < m:
				m = d
		else:
			b = 1
			break
	if b == 1:
		print(0)
	else:
		print(m)


test_cases = int(input())
for itr in range(test_cases):
	n = int(input())
	allEven = True
	array = list(map(int, input().split()))
	temporary = list()
	for i in array:
		if i % 2:
			allEven = False
			print(0)
			break
		else:
			c = 0
			while i % 2 == 0:
				c += 1
				i /= 2
			temporary.append(c)
	if allEven:
		print(min(temporary))


for _ in range(int(input())):
	a = input()
	count = 0
	num = list(map(int, input().split()))
	while all((e % 2 == 0 for e in num)):
		num = [j // 2 for j in num]
		count += 1
	print(count)


try:
	t = int(input())
	for i in range(t):
		z = int(input())
		a = list(map(int, input().split()))
		count = 0
		cnt = 0
		sheela = True
		while sheela:
			for j in range(len(a)):
				if a[j] % 2 == 0:
					a[j] = int(a[j] / 2)
					cnt += 1
				else:
					sheela = False
			if cnt == len(a):
				count += 1
				cnt = 0
		print(count)
except:
	pass


def funcx(n, l1):
	import math
	g = lambda a, b: math.gcd(a, b)
	curr = g(2 ** 29, l1[0])
	if curr == 1:
		return 0
	else:
		for i in range(1, n):
			curr = g(curr, l1[i])
			if curr == 1:
				break
		if curr == 1:
			return 0
		else:
			return int(math.log(curr, 2))
t = int(input())
for i in range(t):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	print(funcx(n, l1))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for j in range(n):
		if l[j] % 2 != 0:
			c = 1
			break
	if c == 1:
		print(0)
	else:
		s = 123456789123456789
		for k in range(n):
			ans = 0
			while l[k] % 2 != 1:
				l[k] = l[k] // 2
				ans += 1
			if ans < s:
				s = ans
		print(s)


import math
from fractions import gcd
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))

	def find_gcd(list):
		x = reduce(gcd, list)
		return x
	if find_gcd(ls) & 1:
		print('0')
	else:
		m = 1000000000.0
		for i in range(n):
			c = 0
			while ls[i] % 2 != 1:
				ls[i] = ls[i] // 2
				c += 1
			m = min(m, c)
		print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	res = 0
	for i in range(n):
		if a[i] % 2 != 0:
			res = 1
			break
	if res == 1:
		print(0)
	else:
		m = 1000000000.0
		for i in range(n):
			c = 0
			while a[i] % 2 != 1:
				a[i] = a[i] // 2
				c += 1
			if c < m:
				m = c
		print(m)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	ans = 0
	for j in a:
		if j % 2 != 0:
			ans = 1
	if ans == 0:
		r = 1000000000
		for k in range(n):
			ans = 0
			while a[k] % 2 == 0:
				a[k] //= 2
				ans += 1
			if ans < r:
				r = ans
		print(r)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 555555
	for i in l:
		c = 0
		while i % 2 == 0:
			i = i / 2
			c = c + 1
		a = min(c, a)
	print(a)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		count = 0
		temp = arr[i]
		while temp % 2 == 0:
			temp = temp / 2
			count += 1
		if i == 0 or count < ans:
			ans = count
	print(ans)


def find(n):
	count = 0
	while n > 0 and n % 2 != 1:
		count += 1
		n //= 2
	return count
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e = 0
	o = 0
	m = 100000000000000
	for i in l:
		if i % 2 == 1:
			o += 1
		else:
			m = min(m, find(i))
			e += 1
	if o == 0:
		print(m)
	else:
		print(0)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	while 1:
		f = 1
		for i in l:
			if i % 2 != 0:
				f = 0
				break
		if f == 0:
			break
		else:
			ans += 1
			for i in range(n):
				l[i] //= 2
	print(ans)


try:
	for _ in range(int(input())):

		def solution():
			N = int(input())
			A = list(input().split())
			for i in range(N):
				A[i] = int(A[i])
			for i in range(N):
				if A[i] % 2 != 0:
					return 0
			n = 0
			while True:
				for i in range(N):
					A[i] = A[i] / 2
				n += 1
				for i in range(N):
					if A[i] % 2 != 0:
						return n
		print(solution())
except:
	pass


t = int(input())
while t != 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = 0
	for i in range(len(arr)):
		count = 0
		while arr[i] % 2 == 0:
			arr[i] /= 2
			count += 1
		if i == 0 or count < ans:
			ans = count
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	ans = max(l)
	for i in range(len(l)):
		a = l[i]
		c = 0
		while a > 1:
			if a & 1:
				break
			else:
				c = c + 1
			a = a >> 1
		if c < ans:
			ans = c
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	best = 10 ** 9
	for i in range(n):
		cnt = 0
		temp = a[i]
		while temp % 2 == 0:
			temp //= 2
			cnt += 1
		best = min(cnt, best)
	print(best)


T = int(input())
for tc in range(T):
	n = int(input())
	l = list(map(int, input().split(' ')))
	c = 1
	m = []
	for i in l:
		if i % 2 != 0:
			print(0)
			c = 0
			break
	if c == 1:
		for i in l:
			d = 0
			while i % 2 == 0 and i > 1:
				i = i // 2
				d += 1
			m.append(d)
		print(min(m))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	l = []
	for i in a:
		c = 0
		while i % 2 == 0:
			c += 1
			i = i // 2
		l.append(c)
	print(min(l))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sol = 10 ** 9
	for i in arr:
		count = 0
		while i % 2 == 0:
			count += 1
			i = i // 2
		if i == 0 or count < sol:
			sol = count
	print(sol)


t = int(input())
for i in range(t):
	n = int(input())
	arr = input().split(' ')
	for j in range(n):
		arr[j] = int(arr[j])
	ans = 0
	while 1:
		tmp = True
		for j in range(n):
			if arr[j] % 2 != 0:
				tmp = False
				break
			arr[j] = int(arr[j] / 2)
		if tmp == False:
			print(ans)
			break
		ans += 1


def rightside1(x):
	count = 0
	while x & 1 == 0:
		count += 1
		x = x >> 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	M = float('inf')
	for i in range(n):
		k = rightside1(a[i])
		M = min(M, k)
	print(M)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = arr[0]
	for i in range(n):
		x = gcd(arr[i], x)
	cnt = 0
	if x % 2 == 0:
		while x % 2 == 0:
			cnt += 1
			x //= 2
		y = cnt
	else:
		y = 0
	print(y)


import math

def solve():
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ans = math.inf
	for i in arr:
		c = 0
		while i % 2 == 0:
			i = i / 2
			c += 1
		ans = min(ans, c)
	print(ans)
t = int(input())
while t:
	solve()
	t -= 1


n = int(input())
for _ in range(n):
	m = int(input())
	ls = list(map(int, input().split()))
	for i in range(m):
		c = 0
		temp = ls[i]
		while temp % 2 == 0:
			temp = temp // 2
			c = c + 1
		if i == 0 or c < mn:
			mn = c
	print(mn)


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

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

def intIn():
	return int(input())
intMax = float('inf')
intMin = float('-inf')
d4x = [1, -1, 0, 0]
d4y = [0, 0, 1, -1]
d8x = [1, -1, 0, 0, -1, -1, 1, 1]
d8y = [0, 0, 1, -1, -1, 1, -1, 1]

def solve():
	n = intIn()
	ar = listIn()
	ans = 0
	s = 0
	for i in ar:
		cnt = 0
		while not i & 1:
			i = i // 2
			cnt += 1
		if s == 0 or cnt < ans:
			ans = cnt
		s += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


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

def listIn():
	return list(map(int, input().split()))
intMax = float('inf')
intMin = float('-inf')
d4x = [1, -1, 0, 0]
d4y = [0, 0, 1, -1]
d8x = [1, -1, 0, 0, -1, -1, 1, 1]
d8y = [0, 0, 1, -1, -1, 1, -1, 1]

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

def solve():
	n = int(input())
	ar = listIn()
	g = ar[0]
	if ar[0] & 1:
		print(0)
		return
	ans = 0
	for i in ar:
		if i & 1 == 1:
			print(0)
			return
		g = gcd(g, i)
	while not g & 1:
		g = g // 2
		ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	for i in b:
		if i % 2 == 1:
			print(0)
			break
	else:
		b.sort()
		g = b[0]
		for i in range(1, a):
			g = gcd(g, b[i])
		x = 0
		while g % 2 == 0:
			g = g // 2
			x += 1
		print(x)


def inInt():
	return int(input())

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

def outList(lst):
	for data in lst:
		print(data)

def outListList(lst):
	for data in lst:
		print(*data)

def solveA():
	result = ['Too Early', 'Too Late', 'Take second dose now']
	for _ in range(inInt()):
		(X, Y, Z) = inIntList()
		ans.append('YES' if X + 2 * Z >= Y else 'NO')

def solveB():
	for _ in range(inInt()):
		(x, y) = inIntList()
		ans.append('NO' if abs(x - y) % 2 else 'YES')

def solveC():
	num = list(range(1, 10 ** 5 + 1))
	for _ in range(inInt()):
		(n, k) = inIntList()
		if n == k:
			ans.append(num[:n])
		elif n - k == 1:
			ans.append([-1])
		else:
			ans.append(num[:k] + [n] + num[k:n - 1])

def solveD():
	for _ in range(inInt()):
		N = inInt()
		A = inIntList()
		ans.append(min((bin(a)[2:][::-1].find('1') for a in A)))
ans = []
solveD()
outList(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = []
	c = float('inf')
	for i in l:
		x = bin(i).replace('0b', '')
		c = min(c, len(x) - len(x.rstrip('0')))
	c = 0 if c == float('inf') else c
	print(c)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	odd = 0
	mini = 100000000000000
	for i in range(n):
		if l[i] % 2 != 0:
			odd += 1
	if odd > 0:
		print(0)
	else:
		for i in range(n):
			count = 0
			while l[i] % 2 == 0:
				count += 1
				l[i] = l[i] // 2
			mini = min(mini, count)
		print(mini)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	yo = False
	x = 0
	while 1:
		for i in range(n):
			if l[i] % 2 == 1:
				print(x)
				yo = True
				break
		for i in range(n):
			l[i] //= 2
		x += 1
		if yo:
			break


from math import floor
t = int(input())
for we in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	k = count = 0
	flag = 1
	for j in l:
		if j % 2 == 1:
			flag = 0
			break
	if flag != 0:
		for i in l:
			while i % 2 == 0:
				k += 1
				i = floor(i / 2)
			if count == 0:
				ans = k
				count = 1
			if k < ans:
				ans = k
			k = 0
	if flag == 0:
		print(0)
	else:
		print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	x = math.gcd(li[0], li[1])
	for i in range(2, n):
		x = math.gcd(x, li[i])
	c = 0
	while x % 2 == 0:
		x = x // 2
		c += 1
	print(c)