You are given an array A = [A_{1}, A_{2}, \ldots, A_{N}], consisting of N integers. In one move, you can take two adjacent numbers A_{i} and A_{i+1}, delete them, and then insert the number A_{i} \land A_{i+1} at the deleted position. Here, \land denotes [bitwise AND]. Note that after this operation, the length of the array decreases by one.

Formally, as long as |A| > 1 (where |A| denotes the current length of A), you can pick an index 1 ≤ i < |A| and transform A into [A_{1}, A_{2}, \ldots, A_{i-1}, A_{i} \land A_{i+1}, A_{i+2}, \ldots, A_{|A|}].

Find the minimum number of moves required to make all numbers in the resulting array equal.

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

- The first line of input contains an integer T — the number of test cases you need to solve.
- The first line of each test case contains one integer N, the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, \ldots, A_{N} — the elements of the array A.

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

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

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

$1 ≤T ≤10^{6}$
$2 ≤N ≤10^{6}$
- Sum of $N$ over all test cases is at most $10^{6}$.
$0 ≤A_{i} < 2^{30}$

------ subtasks ------ 

Subtask 1 (20 points):
$0 ≤A_{i} ≤255$
Sum of $N$ over all test cases is at most $255$.
Subtask 2 (30 points):
Sum of $N$ over all test cases is at most $2000$.
Subtask 3 (50 points):
Original constraints.

----- Sample Input 1 ------ 
4
4
0 0 0 1
2
1 1
6
1 2 3 4 5 6
4
2 28 3 22

----- Sample Output 1 ------ 
1
0
4
3

----- explanation 1 ------ 
Test case $1$: Choose $i = 3$ to make the array $[0, 0, 0 \land 1] = [0, 0, 0]$.

Test case $2$: All elements of the array are already equal.

Test case $3$: One possible sequence of moves is as follows:
- Choose $i = 1$, making the array $[1\land 2, 3, 4, 5, 6] = [0, 3, 4, 5, 6]$
- Choose $i = 2$, making the array $[0, 0, 5, 6]$
- Choose $i = 3$, making the array $[0, 0, 4]$
- Choose $i = 2$, making the array $[0, 0]$

It can be verified that in this case, making every element equal using $3$ or fewer moves is impossible.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = arr[0]
	for i in arr:
		res &= i
	p = 0
	curr = arr[0]
	for i in range(1, n):
		if curr == res:
			p += 1
			curr = arr[i]
		else:
			curr &= arr[i]
	if curr == res:
		p += 1
	print(n - p)


from functools import reduce
n = int(input())
for i in range(n):
	length = int(input())
	A = list(map(int, input().split()))
	minim = reduce(lambda a, b: a & b, A)
	ans = len(A)
	t = 2 ** 31 - 1
	for j in range(len(A)):
		t &= A[j]
		if t == minim:
			ans -= 1
			t = 2 ** 31 - 1
	print(ans)


from functools import reduce
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	cum = reduce(lambda x, y: x & y, arr)
	operation = n - 1
	temp = 2 ** 31 - 1
	j = 0
	while j < len(arr):
		temp &= arr[j]
		if temp == cum:
			operation -= 1
			temp = 2 ** 31 - 1
		j += 1
	print(operation + 1)


ans = ''
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = (1 << 31) - 1
	for i in arr:
		res &= i
	count = 0
	cur = (1 << 31) - 1
	for i in range(n):
		if cur & arr[i] == res:
			count += 1
			cur = (1 << 31) - 1
		else:
			cur &= arr[i]
	ans += str(n - count) + '\n'
print(ans)


for p in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	res = l[0]
	for ele in l:
		res = res & ele
	ans = 0
	m = []
	i = 0
	for ele in l:
		if ele == res:
			m.append(ele)
		elif len(m) == 0:
			m.append(ele)
		elif m[-1] != res:
			t = m[-1]
			m.pop()
			m.append(ele & t)
			ans += 1
		else:
			m.append(ele)
		i += 1
	for ele in m:
		if ele != res:
			ans += 1
	print(ans)


T = int(input())
for ts in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	k = A[0]
	for i in range(1, N):
		k &= A[i]
	ans = 0
	local = A[0]
	for i in range(1, N):
		if local == k:
			local = A[i]
		else:
			local &= A[i]
			ans += 1
	if local != k:
		ans += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	for i in range(1, n):
		x = x & a[i]
	c = a[0]
	cc = 0
	for i in range(1, n):
		if c == x:
			cc += 1
			c = a[i]
		c = c & a[i]
	if c == x:
		cc += 1
	print(n - cc)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	count = 0
	z = []
	check1 = 2 ** 30 - 1
	for i in lis:
		check1 &= i
	check2 = 2 ** 32 - 1
	for i in lis:
		check2 &= i
		if check2 == check1:
			count += 1
			check2 = 2 ** 32 - 1
	print(len(lis) - count)


def fi():
	return int(input())

def li():
	return list(map(int, input().split()))
t = fi()
for i in range(t):
	n = fi()
	a = li()
	tand = (1 << 30) - 1
	for i in range(len(a)):
		tand &= a[i]
	groups = 0
	cand = (1 << 30) - 1
	for i in range(len(a)):
		cand &= a[i]
		if cand == tand:
			groups += 1
			cand = (1 << 30) - 1
	ans = len(a) - groups
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = (1 << 30) - 1
	for i in range(n):
		x &= a[i]
	g = 0
	c = (1 << 30) - 1
	for i in range(n):
		c &= a[i]
		if c == x:
			g += 1
			c = (1 << 30) - 1
	print(n - g)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	x = (1 << 30) - 1
	for i in range(n):
		x &= arr[i]
	y = (1 << 30) - 1
	for i in range(n):
		y &= arr[i]
		if y == x:
			c += 1
			y = (1 << 30) - 1
	print(n - c)


t = int(input())
for test in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	ans = 0
	r = v[0]
	for i in range(0, n):
		r &= v[i]
	for i in range(0, n - 1):
		if v[i] != r:
			ans += 1
			v[i + 1] &= v[i]
	if v[n - 1] != r:
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	total_and = (1 << 30) - 1
	for i in range(n):
		total_and &= a[i]
	group_and = (1 << 30) - 1
	for i in range(n):
		group_and &= a[i]
		if group_and == total_and:
			g += 1
			group_and = (1 << 30) - 1
	print(n - g)


t = int(input())
for x in range(t):
	n = int(input())
	seq = list(map(int, input().split()))
	Big = 2 ** 31 - 1
	totAnd = Big
	for i in seq:
		totAnd = totAnd & i
	groups = 0
	CurrAnd = Big
	for i in seq:
		CurrAnd = CurrAnd & i
		if CurrAnd == totAnd:
			groups += 1
			CurrAnd = Big
	print(n - groups)


result = []
ones = 2 ** 30 - 1
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	ad = ones
	for a in A:
		ad &= a
	(tmp, c) = (ones, 0)
	ans = 0
	for a in A:
		tmp &= a
		if tmp == ad:
			ans += c
			(tmp, c) = (ones, 0)
		else:
			c += 1
	if tmp != ad:
		ans += c
	result.append(ans)
print(*result, sep='\n')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	fe = arr[0]
	for x in arr[1:]:
		fe &= x
	ng = 0
	ta = arr[0]
	for (i, x) in enumerate(arr):
		ta &= x
		if ta == fe:
			ng += 1
			if i + 1 < n:
				ta = arr[i + 1]
	print(n - ng)


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


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	s = A[0]
	res = 0
	S = A[0]
	for i in A:
		S = S & i
	for i in range(1, N):
		if s == S:
			s = A[i]
			res += 1
		s = s & A[i]
	if s == S:
		res += 1
	print(N - res)


r = int(input())
while r != 0:
	r -= 1
	n = int(input())
	a = list(map(int, input().split()))
	x = (1 << 30) - 1
	for i in a:
		x = x & i
	y = (1 << 30) - 1
	c = 0
	for i in a:
		y = y & i
		if y == x:
			c += 1
			y = (1 << 30) - 1
	print(n - c)


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	a = L()
	x = 2 ** 30 - 1
	for i in a:
		x &= i
	i = 1
	while i < n:
		if a[i - 1] == x:
			i += 1
			continue
		a[i] &= a[i - 1]
		if a[i] == x:
			i += 1
		i += 1
	i = n - 1
	print(n - a.count(x))


for T in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	bitAND = l[0]
	for i in range(n):
		bitAND &= l[i]
	smolbitAND = l[0]
	count = 0
	for i in range(n):
		smolbitAND &= l[i]
		if smolbitAND == bitAND and i != n - 1:
			count += 1
			smolbitAND = l[i + 1]
		elif smolbitAND == bitAND and i == n - 1:
			count += 1
	print(n - count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = l[0]
	for i in l:
		t &= i
	ct = 2 ** 30 - 1
	grps = 0
	for i in l:
		ct &= i
		if ct == t:
			grps += 1
			ct = 2 ** 30 - 1
	print(n - grps)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	finaland = currentand = arr[0]
	for i in range(n):
		finaland &= arr[i]
	count = 0
	arr.append(0)
	for i in range(n):
		currentand &= arr[i]
		if currentand == finaland:
			count += 1
			currentand = arr[i + 1]
	print(n - count)


for t in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	val = ar[0]
	for i in range(1, len(ar)):
		val &= ar[i]
	part = 0
	x = (1 << 30) - 1
	for i in ar:
		x &= i
		if x == val:
			part += 1
			x = (1 << 30) - 1
	print(n - part)


from sys import stdin, setrecursionlimit, stdout
from io import BytesIO
import os
from collections import deque, Counter, defaultdict
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
from bisect import bisect_right, bisect_left

def ii():
	return int(input().decode()) if OJ else int(input())

def fi():
	return float(input().decode()) if OJ else float(input())

def mi():
	return map(int, input().decode().split()) if OJ else map(int, input().split())

def fmi():
	return map(float, input().decode().split()) if OJ else map(float, input().split(''))

def li():
	return list(mi())

def si():
	return input().decode().rstrip() if OJ else input().rstrip()

def lsi():
	return list(si())

def oj():
	global OJ
	OJ = True

def main():
	n = ii()
	a = li()
	tot = a[0]
	for i in a:
		tot &= i
	cnt = i = 0
	while i < n:
		cur = a[i]
		j = i + 1
		while j < n and cur != tot:
			cur &= a[j]
			j += 1
		if cur == tot:
			cnt += 1
		i = j
	print(n - cnt)
OJ = False
if OJ:
	input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
else:
	input = stdin.readline
vow = {'A', 'E', 'I', 'O', 'U'}
mod = 1000000007
res = ['NO', 'YES']
(test, test_case) = (0, 1)
test_case = ii()
while test < test_case:
	test += 1
	main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	z = a[0]
	for i in range(1, n):
		z = z & a[i]
	r = 0
	for i in range(n):
		if a[i] == z:
			continue
		if i == n - 1:
			r += 1
			continue
		a[i + 1] = a[i] & a[i + 1]
		r += 1
	print(r)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = (1 << 30) - 1
	for i in a:
		mx &= i
	grp = 0
	curAnd = (1 << 30) - 1
	for i in range(n):
		curAnd &= a[i]
		if curAnd == mx:
			grp += 1
			curAnd = (1 << 30) - 1
	print(n - grp)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = arr[0]
	for j in range(1, n):
		x = x & arr[j]
	j = 0
	c = 0
	while j < n:
		y = arr[j]
		j += 1
		if y == 0:
			continue
		while y != x and j < n:
			y = y & arr[j]
			j += 1
			c += 1
	if y != x:
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	least = (1 << 30) - 1
	for i in lis:
		least &= i
	p = lis[0]
	i = 1
	counti = 0
	while i < n:
		if p == least:
			p = lis[i]
			counti += 1
		else:
			p &= lis[i]
		i += 1
	if p == least:
		counti += 1
	print(n - counti)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	bit = a[0]
	for i in range(1, n):
		bit = bit & a[i]
	ans = 0
	left = int('1' * 32, 2)
	for i in range(n):
		left = left & a[i]
		if left == bit:
			left = int('1' * 32, 2)
		else:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = arr[0]
	for i in range(1, n):
		a &= arr[i]
	c = 0
	for i in range(n):
		if arr[i] == a:
			c += 1
	c = n - c
	ans = 0
	for i in range(n):
		if arr[i] == a:
			continue
		if i == n - 1:
			ans += 1
			continue
		arr[i + 1] &= arr[i]
		ans += 1
	print(ans)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

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

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	j = len(s) - 1
	i = 0
	while j > i:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def solve(t):
	n = readInts()
	ar = readList()
	k = ar[0]
	for i in range(1, n):
		k = k & ar[i]
	cnt = 0
	for (i, num) in enumerate(ar):
		if num == k:
			continue
		if i == n - 1:
			cnt += 1
			break
		ar[i + 1] = ar[i] & ar[i + 1]
		cnt += 1
	print(cnt)

def main():
	t = 1
	sys.setrecursionlimit(10000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	b = arr[0]
	for i in range(n):
		b &= arr[i]
	r = 0
	for i in range(n):
		if arr[i] == b:
			continue
		if i == n - 1:
			r = r + 1
			continue
		arr[i + 1] &= arr[i]
		r += 1
	print(r)


tc = int(input())
while tc:
	n = int(input())
	a = list(map(int, input().split()))[:n]
	t = 2 ** 30 - 1
	for i in a:
		t = t & i
	ans = 0
	c = 2 ** 30 - 1
	for i in a:
		c &= i
		if c == t:
			ans += 1
			c = 2 ** 30 - 1
	print(n - ans)
	tc -= 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = a[0]
	for i in range(n):
		m &= a[i]
	ans = 0
	for i in range(n):
		if a[i] == m:
			continue
		if i == n - 1:
			ans += 1
			continue
		ans += 1
		a[i + 1] &= a[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = -1
	for i in range(n):
		a = a & l[i]
	t = -1
	ct = 0
	for j in range(n):
		t = t & l[j]
		if t == a:
			ct += 1
			t = -1
	print(n - ct)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[0]
	for i in range(n):
		b &= a[i]
	x = 0
	for i in range(n):
		if a[i] == b:
			x += 1
	x = n - x
	r = 0
	for i in range(n):
		if a[i] == b:
			continue
		if i == n - 1:
			r += 1
			continue
		a[i + 1] &= a[i]
		r += 1
	print(r)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	req_num = arr[0]
	for i in arr:
		req_num &= i
	temp = arr[0]
	grps = 0
	for i in range(n):
		temp &= arr[i]
		if temp == req_num:
			if i < n - 1:
				temp = arr[i + 1]
			grps += 1
	print(n - grps)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	tot = -1
	for i in range(n):
		tot &= arr[i]
	cur = -1
	ans = 0
	for i in range(n):
		cur &= arr[i]
		if cur == tot:
			cur = -1
			ans += 1
	print(n - ans)
	t -= 1


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	a = (1 << 30) - 1
	for i in range(N):
		a &= arr[i]
	curr = (1 << 30) - 1
	ans = 0
	for i in range(N):
		curr &= arr[i]
		if curr == a:
			ans += 1
			curr = (1 << 30) - 1
	print(N - ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	x = arr[0]
	for i in arr[1:]:
		x &= i
	g = 0
	c = (1 << 30) - 1
	for i in arr:
		c &= i
		if c == x:
			g += 1
			c = (1 << 30) - 1
	print(n - g)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	grps = 0
	p = 2 ** 30 - 1
	c = 2 ** 30 - 1
	for i in l:
		p &= i
	for i in l:
		c &= i
		if c == p:
			grps += 1
			c = 2 ** 30 - 1
	print(n - grps)


t = int(input())
for i in range(t):
	n = int(input())
	l = list([int(x) for x in input().split()])
	a = (1 << 32) - 1
	for i in l:
		a = a & i
	c = 0
	ans = 0
	b = (1 << 32) - 1
	for i in l:
		b = b & i
		c += 1
		if b == a:
			ans += c - 1
			c = 0
			b = (1 << 32) - 1
	if c > 0:
		ans += c
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = l[0]
	for j in range(1, n):
		x = x & l[j]
	ans = 0
	for k in range(n):
		if l[k] == x:
			continue
		if k == n - 1:
			ans += 1
			continue
		l[k + 1] = l[k] & l[k + 1]
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(j) for j in input().split()]
	x = l[0]
	for i in range(1, n):
		x = x & l[i]
	ans = 0
	for i in range(n):
		if l[i] == x:
			continue
		if i == n - 1:
			ans += 1
			continue
		l[i + 1] = l[i] & l[i + 1]
		ans += 1
	print(ans)


from functools import reduce
from operator import and_
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = reduce(and_, arr)
	ans = 0
	for i in range(n):
		if arr[i] == a:
			continue
		if i == n - 1:
			ans += 1
			continue
		arr[i + 1] &= arr[i]
		ans += 1
	print(ans)


tc = int(input())

def reset():
	return (1 << 30) - 1
for t in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	req = reset()
	for i in a:
		req &= i
	ans = 0
	cur = reset()
	for i in a:
		cur &= i
		if cur == req:
			cur = reset()
			ans += 1
	print(n - ans)


from functools import reduce
k = int(input())
while k:
	n = int(input())
	li = list(map(int, input().split()))
	and_ = reduce(lambda x, y: x & y, li)
	x = -1
	ans = 0
	for i in range(n):
		x &= li[i]
		ans += 1
		if x == and_:
			x = -1
			ans -= 1
	print(ans)
	k = k - 1


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

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

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

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

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

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

def myceil(x, y):
	return (x + y - 1) // y

def Solution():
	pass

def main():
	for _ in range(get_int()):
		n = get_int()
		a = get_ints_in_list()
		s = a[0]
		for v in a:
			s &= v
		i = 0
		cnt = 0
		ts = a[i]
		while i < n:
			if ts & a[i] == s:
				cnt += 1
				i += 1
				if i < n:
					ts = a[i]
			else:
				ts &= a[i]
				i += 1
		print(n - cnt)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mn = a[0]
	for i in range(1, n):
		mn &= a[i]
	tm = 0
	for i in range(n):
		if a[i] == mn:
			tm += 1
	tm = n - tm
	ans = 0
	for i in range(n):
		if a[i] == mn:
			continue
		if i == n - 1:
			ans += 1
			continue
		a[i + 1] &= a[i]
		ans += 1
	print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		res = arr[0]
		for i in range(n):
			res &= arr[i]
		ans = 0
		for i in range(n - 1):
			if arr[i] == res:
				continue
			arr[i + 1] &= arr[i]
			ans += 1
		if arr[-1] != res:
			ans += 1
		print(ans)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split(' ')))
	c = 0
	a = sorted(x)
	if len(set(a)) == 1:
		print(0)
	else:
		d = x[0]
		for i in range(1, n):
			d &= x[i]
		for i in range(n):
			if x[i] == d:
				continue
			elif i == n - 1:
				c = c + 1
			else:
				x[i + 1] &= x[i]
				c = c + 1
		print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	bc = [0] * 32
	for i in a:
		for j in range(32):
			if i >> j & 1:
				bc[j] += 1
	t = 0
	for (i, j) in enumerate(bc):
		if j == n:
			t |= 1 << i
	c = 0
	p = a[0]
	for i in range(1, n):
		if p == t:
			p = a[i]
		else:
			p &= a[i]
			c += 1
	if p != t:
		c += 1
	print(c)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	finalAnd = A[0]
	for a in A[1:]:
		finalAnd &= a
	groups = 0
	curr = A[0]
	for i in range(1, n):
		if curr == finalAnd:
			groups += 1
			curr = A[i]
		else:
			curr &= A[i]
	if curr == finalAnd:
		groups += 1
	print(n - groups)
t = int(input())
while t != 0:
	solve()
	t -= 1


def solve(n, arr):
	x = arr[0]
	for i in range(n):
		x &= arr[i]
	groups = 0
	s = arr[0]
	for i in range(n):
		s &= arr[i]
		if s == x:
			groups += 1
			if i < n - 1:
				s = arr[i + 1]
	return n - groups
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


from sys import stdin, stdout
from collections import defaultdict, Counter, deque
import math, heapq, bisect
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	x = a[0]
	for i in range(1, n):
		x = x & a[i]
	groups = 0
	queue = deque()
	i = 0
	while i < n:
		ele = a[i]
		queue.append(ele)
		if len(queue) == 1:
			curr = ele
		else:
			curr = curr & ele
		if curr == x:
			groups += 1
			queue.clear()
		i += 1
	print(n - groups)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = a[0]
	for i in a:
		k &= i
	a.append(k)
	(tp, ct, r) = (a[0], 0, 0)
	for i in a:
		ct += 1
		tp &= i
		if tp == k:
			r += ct - 1
			ct = 0
			tp = 2 ** 30 - 1
	print(r)


t = int(input())
for i in range(t):
	a = int(input())
	n = list(map(int, input().split()))
	cnt = 0
	if len(set(n)) == 1:
		print(0)
	else:
		d = n[0]
		for i in range(1, len(n)):
			d &= n[i]
		for i in range(a):
			if n[i] == d:
				continue
			elif i == a - 1:
				cnt += 1
				continue
			else:
				n[i + 1] &= n[i]
				cnt += 1
		print(cnt)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = a[0]
	for i in a:
		k &= i
	count = 0
	for i in range(n - 1):
		if a[i] == k:
			continue
		a[i + 1] &= a[i]
		count += 1
	print(count + (a[-1] != k))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = l[0]
	for i in range(1, n):
		t &= l[i]
	g = 0
	c = 2 ** 30 - 1
	for i in range(n):
		c &= l[i]
		if c == t:
			g += 1
			c = 2 ** 30 - 1
	print(n - g)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if len(set(l)) == 1:
		print(0)
	else:
		c = 0
		a = 0
		e = l[0]
		for i in range(1, n):
			e &= l[i]
		for i in range(n):
			if l[i] == e:
				continue
			elif i == n - 1:
				a += 1
				continue
			else:
				l[i + 1] &= l[i]
				a += 1
		print(a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ele = a[0]
	for i in range(1, n):
		ele = ele & a[i]
	noz = a.count(ele)
	calc = 0
	i = 0
	while i < n - 1:
		if a[i] == ele:
			i = i + 1
			continue
		a[i + 1] = a[i] & a[i + 1]
		calc = calc + 1
		i = i + 1
	if a[-1] == ele:
		print(calc)
	else:
		print(calc + 1)


from sys import stdin

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

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

def li():
	return list(mi())

def si():
	return stdin.readline()
t = 1
t = ii()
for _ in range(t):
	n = ii()
	l1 = li()
	ans = l1[0]
	for i in l1[1:]:
		ans &= i
	if l1.count(ans) == n:
		print(0)
		continue
	c1 = 0
	curr = l1[0]
	for i in l1[1:]:
		if curr != ans:
			curr &= i
			c1 += 1
		else:
			curr = i
	if curr != ans:
		c1 += 1
	c2 = 0
	l1 = l1[::-1]
	curr = l1[0]
	for i in l1[1:]:
		if curr != ans:
			curr &= i
			c2 += 1
		else:
			curr = i
	if curr != ans:
		c2 += 1
	print(min(c1, c2))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	mn = a[0]
	for i in range(1, n):
		mn = mn & a[i]
	ans = 0
	for i in range(n):
		if a[i] == mn:
			continue
		if i == n - 1:
			ans += 1
			break
		if a[i] != mn:
			a[i + 1] = a[i] & a[i + 1]
			ans += 1
	print(ans)