You are given an array $a$ of $n$ elements. You can apply the following operation to it any number of times:

Select some subarray from $a$ of even size $2k$ that begins at position $l$ ($1\le l \le l+2\cdot{k}-1\le n$, $k \ge 1$) and for each $i$ between $0$ and $k-1$ (inclusive), assign the value $a_{l+k+i}$ to $a_{l+i}$.

For example, if $a = [2, 1, 3, 4, 5, 3]$, then choose $l = 1$ and $k = 2$, applying this operation the array will become $a = [3, 4, 3, 4, 5, 3]$.

Find the minimum number of operations (possibly zero) needed to make all the elements of the array equal.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array.

The second line of each test case consists of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

Print $t$ lines, each line containing the answer to the corresponding test case — the minimum number of operations needed to make equal all the elements of the array with the given operation.


-----Examples-----

Input
5
3
1 1 1
2
2 1
5
4 4 4 2 4
4
4 2 1 3
1
1
Output
0
1
1
2
0


-----Note-----

In the first test, all elements are equal, therefore no operations are needed.

In the second test, you can apply one operation with $k=1$ and $l=1$, set $a_1 := a_2$, and the array becomes $[1, 1]$ with $1$ operation.

In the third test, you can apply one operation with $k=1$ and $l=4$, set $a_4 := a_5$, and the array becomes $[4, 4, 4, 4, 4]$.

In the fourth test, you can apply one operation with $k=1$ and $l=3$, set $a_3 := a_4$, and the array becomes $[4, 2, 3, 3]$, then you can apply another operation with $k=2$ and $l=1$, set $a_1 := a_3$, $a_2 := a_4$, and the array becomes $[3, 3, 3, 3]$.

In the fifth test, there is only one element, therefore no operations are needed.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Greedy algorithms


Solutions:
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	l = stdin.readline().split()
	l.reverse()
	(c, i, a) = (0, 1, l[0])
	while True:
		if i >= n:
			break
		if l[i] == a:
			i += 1
		else:
			i *= 2
			c += 1
	print(c)


import sys
int1 = lambda x: int(x) - 1
pDB = lambda *x: print(*x, end='\n', file=sys.stderr)
p2D = lambda x: print(*x, sep='\n', end='\n\n', file=sys.stderr)

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
inf = 18446744073709551615
md = 998244353

def solve():
	n = II()
	aa = LI()
	aa.reverse()
	i = 1
	ans = 0
	while 1:
		while i < n and aa[i] == aa[0]:
			i += 1
		if i >= n:
			break
		ans += 1
		i *= 2
	print(ans)
for testcase in range(II()):
	solve()


import sys

def solution(a):
	n = len(a)
	a.reverse()
	a.insert(0, 0)
	if n <= 1:
		print(0)
		return
	moves = 0
	num = a[1]
	index = 1
	while index < n:
		if a[index + 1] == num:
			index += 1
		else:
			moves += 1
			index *= 2
	print(moves)
t = None
a = []
b = []
input = sys.stdin.read().splitlines()
t = int(input[0])
offset = 1
for test in range(t):
	a = input[2 * test + 1 + offset]
	a = a.split(' ')
	a = [int(ele) for ele in a]
	solution(a)


for s in [*open(0)][2::2]:
	a = s.split()
	i = j = -1
	r = 0
	while -j < len(a):
		if a[j - 1] != a[-1]:
			r += 1
			i = j = j * 2
		else:
			j -= 1
	print(r)


import sys

def main():
	inp = sys.stdin
	outp = sys.stdout
	t = int(inp.readline().strip())
	ans = []
	for _ in range(t):
		n = int(inp.readline().strip())
		a = list(map(int, inp.readline().strip().split()))
		k = 1
		ops = 0
		while 2 * k <= n:
			while 2 * k <= n and a[-(k + 1)] == a[-k]:
				k += 1
			if 2 * k <= n:
				a[-2 * k:-k] = a[-k:]
				ops += 1
				k *= 2
		if a[:k] != a[-k:]:
			ops += 1
		ans.append(ops)
	outp.write('\n'.join(list(map(str, ans))))
main()


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

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

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

def read_list():
	s = input()
	return list(s[:len(s) - 1])

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

def solve(a):
	ans = 0
	if len(a) == 1:
		return ans
	n = len(a) - 1
	i = n - 1
	while i >= 0:
		if a[i] == a[n]:
			i -= 1
		else:
			ans += 1
			i -= n - i
	return ans
for _ in range(inp()):
	_ = inp()
	print(solve(read_int_list()))


def check_amount_of_rep_from_back(l, k, n):
	am_ = 0
	num = n
	for i in range(k, -1, -1):
		if l[i] != num:
			break
		am_ += 1
	return am_
cases = int(input())
answers = []
for _ in range(cases):
	len_arr = int(input())
	l = input().split(' ')
	last = l[-1]
	amt_ = check_amount_of_rep_from_back(l, len_arr - 1, last)
	turns = 0
	while amt_ < len_arr:
		amt_ *= 2
		amt_ += check_amount_of_rep_from_back(l, len_arr - 1 - amt_, last)
		turns += 1
	answers.append(str(turns))
print('\n'.join(answers))


import sys
import math
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	i = n - 2
	count = 1
	ans = 0
	while i >= 0:
		if a[i] == a[-1]:
			i -= 1
		else:
			ans += 1
			i -= n - i - 1
	print(ans)


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	length = inp()
	arr = inlt()
	target = arr[-1]
	count = 0
	i = length - 2
	while i >= 0:
		if arr[i] == target:
			i -= 1
			continue
		count += 1
		i = length - 1 - (length - i - 1) * 2
	print(count)


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	i = n - 1
	c = 0
	f = 0
	while i > -1:
		if a[i] == a[-1]:
			f = f + 1
			i = i - 1
		else:
			i = i - f
			f = 2 * f
			c = c + 1
	print(c)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = input()[:-1].split()
	i = -1
	c = 0
	while -i < len(a):
		if a[i - 1] != a[-1]:
			c += 1
			i *= 2
		else:
			i -= 1
	print(c)


import sys
from collections import deque
input = sys.stdin.readline

def solution() -> int:
	queue = deque()
	a_list.reverse()
	std_num = a_list[0]
	for (idx, val) in enumerate(a_list, start=1):
		if val != std_num:
			queue.append(idx)
	cnt = 0
	boundary = 0
	while len(queue):
		pos = queue.popleft()
		if pos > boundary:
			cnt += 1
			boundary = (pos - 1) * 2
	return cnt
t = int(input())
for tc in range(t):
	n = int(input())
	a_list = list(map(int, input().split()))
	sol = solution()
	print(sol)


import sys
inputs = sys.stdin.readlines()
for idx in range(1, len(inputs), 2):
	l = list(map(int, inputs[idx + 1].split()))
	v = l[-1]
	ans = 0
	i = 1
	while i < len(l) + 1:
		if l[-i] != v:
			ans += 1
			i = (i - 1) * 2 + 1
		else:
			i += 1
	print(ans)


import sys
input = sys.stdin.readline

def solve(n, arr):
	i = n - 2
	jump = 1
	ans = 0
	val = arr[-1]
	while i >= 0:
		if arr[i] == val:
			i -= 1
			jump += 1
			continue
		i -= jump
		jump *= 2
		ans += 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1 or len(set(a)) == 1:
		print(0)
		continue
	print(solve(n, a))


import sys
import bisect
inp = sys.stdin.readline

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

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	n = int(inp())
	a = [int(i) for i in inp().split()]
	i = n - 2
	ans = 0
	while i >= 0:
		if a[i] != a[i + 1]:
			ans += 1
			i = i - (n - 1 - i)
			a[i + 1] = a[-1]
		else:
			i -= 1
	print(ans)


for s in [*open(0)][2::2]:
	lst = [*map(int, s.split())]
	lst.reverse()
	sz = len(lst)
	i = 0
	op = 0
	while i < sz:
		if lst[i] == lst[0]:
			i += 1
			continue
		op += 1
		i *= 2
	print(op)


import sys
import math
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def solution(N, A):
	A.reverse()
	if N == 1:
		return 0
	ans = 0
	(p, l) = (A[0], 1)
	while l < N:
		while l < N:
			if p != A[l]:
				l -= 1
				break
			l += 1
		if l == N:
			break
		r = (l << 1) + 1
		if r >= N:
			r = N - 1
		for i in range(l + 1, r + 1):
			if A[i] != p:
				ans += 1
				break
		A[r] = p
		l = r
	return ans
R = []
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input()[:-1].split()))
	R.append(solution(n, a))
for r in R:
	print(r)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	i = n - 2
	magicnumber = arr[-1]
	ans = 0
	while i > -1:
		if arr[i] != magicnumber:
			ans += 1
			i = n - 2 * (n - i - 1) - 1
		else:
			i -= 1
	print(ans)


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	arr = [int(x) for x in input().split()]
	last_element = arr[-1]
	run_length = 1
	num_doubles = 0
	while run_length < n:
		while run_length < n and arr[~run_length] == last_element:
			run_length += 1
		if run_length == n:
			break
		run_length *= 2
		num_doubles += 1
	print(num_doubles)


def get_ops(a):
	count = 0
	if len(a) <= 1:
		return 0
	i = len(a) - 1
	while i >= 0:
		if a[i] != a[-1]:
			count += 1
			i -= len(a) - i - 1
		else:
			i -= 1
	return count
subs = input()
subs = int(subs)
results = []
for i in range(subs):
	N = input()
	N = str(N)
	a = input()
	a = list(map(int, a.split()))
	results.append(get_ops(a))
for n in results:
	print(n)


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[n - 1]
	cnt = 0
	length = 1
	j = n - 2
	while j >= 0:
		while j >= 0 and a[j] == x:
			length += 1
			j -= 1
		if j < 0:
			break
		cnt += 1
		j = j - length
		length *= 2
	ans.append(cnt)
for i in ans:
	print(i)


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	cnt = 1
	i = n - 2
	ans = 0
	while i >= 0:
		if a[i] == a[-1]:
			cnt += 1
			i -= 1
		else:
			ans += 1
			i -= cnt
			cnt *= 2
	print(ans)


ans = []
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = a[n - 1]
	kol = 0
	i = n - 1
	otv = 0
	while i >= 0:
		if a[i] == k:
			kol += 1
		else:
			otv += 1
			i -= kol - 1
			kol *= 2
		i -= 1
	ans.append(otv)
print('\n'.join([str(i) for i in ans]))


import sys, collections

def solve(n, A):
	goal = A[n - 1]
	operation = 0
	leftmost = n - 1
	for i in range(n - 2, -1, -1):
		if A[i] == goal or leftmost <= i:
			continue
		operation += 1
		k = n - i - 1
		leftmost = i + 1 - k
	return operation
input = sys.stdin.readline
tests = int(input()[:-1])
for test in range(tests):
	n = int(input()[:-1])
	A = [int(s) for s in input()[:-1].split()]
	print(solve(n, A))


from sys import stdin

def solve():
	for _ in range(int(stdin.readline().strip())):
		n = int(stdin.readline().rstrip())
		a = list(map(int, stdin.readline().rstrip().split()))[::-1]
		x = a[0]
		flag = 1
		for i in range(n):
			if a[i] != x:
				flag = 0
				break
		if flag:
			print(0)
			continue
		ans = 0
		k = 2
		while i < n:
			while i < n and a[i] == x:
				i += 1
			flag = 0
			for j in range(i, min(2 * i, n)):
				if a[j] != x:
					flag = 1
					break
			if flag:
				ans += 1
			i *= 2
		print(ans)
solve()


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	lst = list(map(int, input().split()))
	x = lst[-1]
	idx = n - 1
	cnt = 0
	while idx >= 0:
		while idx >= 0 and lst[idx] == lst[-1]:
			idx -= 1
		if idx < 0:
			break
		idx -= n - 1 - idx
		cnt += 1
		idx = max(-1, idx)
	print(cnt)


cases = range(int(input()))
func = lambda : [int(q) for q in input().split()]
ans = []
for c in cases:
	length = int(input())
	arr = func()
	operation_counter = 0
	n = 1
	if length == 1:
		pass
	else:
		while arr[-1] == arr[-1 - n]:
			if n >= (length + 1) // 2:
				break
			n += 1
		while n < length:
			if arr[-1 - n] == arr[-1]:
				n += 1
			else:
				n *= 2
				operation_counter += 1
	ans.append(operation_counter)
for q in ans:
	print(q)


import sys
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	n = int(input())
	ans = 0
	arr1 = [int(item) for item in input().split()]
	arr1.reverse()
	i = 1
	while True:
		for x in range(i, n):
			if i > n or arr1[x] != arr1[0]:
				break
			if arr1[x] == arr1[0]:
				i += 1
		if i >= n:
			break
		else:
			ans += 1
			i *= 2
	print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	i = n - 1
	c = a[-1]
	x = 1
	while i > 0:
		if a[i] == a[i - 1]:
			x = x + 1
		else:
			break
		i = i - 1
	if x == n:
		print(0)
	else:
		ans = 0
		while 2 * x < n:
			for i in range(n - 2 * x, n - x):
				a[i] = c
			x = x * 2
			if a[n - x - 1] == c:
				o = n - x - 1
				while o > 0:
					if a[o] == c:
						x = x + 1
					else:
						break
					o = o - 1
			ans = ans + 1
			if a.count(c) == n:
				break
		if a.count(c) != n:
			ans = ans + 1
		print(ans)


answer = ''
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 != 0:
		n += 1
		a = [a[0]] + a
	count = [0] * (n + 1)
	for i in range(n - 1, n // 2 - 1, -1):
		if a[i] == a[i - 1]:
			count[i] = count[i + 1]
		else:
			count[i] = count[i + 1] + bool(a[i:n] != a[2 * i - n:i])
			a[2 * i - n:i] = a[i:n]
	if a[0:n // 2] != a[n // 2:2 * (n // 2)]:
		count[n // 2] += 1
	answer += '%d\n' % count[n // 2]
print(answer.strip())


def function(n, arr):
	count = 0
	if n == 1:
		return count
	curr = 1
	i = n - 2
	val = arr[n - 1]
	while i > -1:
		if arr[i] == val:
			curr += 1
			i -= 1
		else:
			count += 1
			i -= curr
			curr = 2 * curr
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(function(n, arr))


t = int(input())
for _ in range(t):
	n = int(input())
	l = input().split()
	if n == 0 or n == 1:
		print(0)
		continue
	count = 0
	equal = l[n - 1]
	if l[n - 2] != equal:
		count += 1
	i = n - 3
	while i >= 0:
		if l[i] != equal:
			count += 1
			i -= n - 1 - i
			continue
		i -= 1
	print(count)


for i in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	num = num[::-1]
	x = 1
	ans = 0
	while x < n:
		if num[x] == num[0]:
			x += 1
			continue
		x *= 2
		ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = [0] + a[::-1]
	p = a[1]
	i = 1
	ans = 0
	while i < n + 1:
		if a[i] == p:
			i += 1
		else:
			i = (i - 1) * 2 + 1
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 1
	doubles = 0
	while True:
		while i < n and a[-1] == a[-i - 1]:
			i += 1
		if i >= n:
			break
		i *= 2
		doubles += 1
	print(doubles)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	i = n - 1
	ans = 0
	num = A[-1]
	while i >= 0:
		if A[i] == num:
			i -= 1
		else:
			lenn = n - 1 - i
			i -= lenn
			ans += 1
			if i < 0:
				break
	print(ans)


def solve(a):
	l = len(a)
	i = l - 2
	c = 0
	while i >= 0:
		if a[i] != a[-1]:
			c += 1
			i -= l - i - 1
		else:
			i -= 1
	return c
n = int(input())
for i in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	if m == 1:
		print(0)
	else:
		print(solve(a))


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	a = list(map(int, input().split()))
	i = n - 2
	while i >= 0:
		d = n - 1 - i
		if a[i] != a[n - 1]:
			c += 1
			i = i - d
		else:
			i = i - 1
	print(c)


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	n = len(arr)
	curr = 0
	el = arr[-1]
	le = 0
	steps = 0
	i = n - 1
	ok = 0
	while i >= 0:
		if arr[i] == el:
			curr += 1
			le = 0
			i -= 1
		else:
			curr += curr
			steps += 1
			i = n - curr - 1
	print(steps)


from math import log, ceil
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	i = n - 2
	step = 1
	while i >= 0:
		if a[i] != a[-1]:
			count += 1
			i -= step
			step *= 2
		else:
			step += 1
			i -= 1
	print(count)


def fun(n, arr):
	result = 0
	last = arr[-1]
	i = n - 2
	while i > -1:
		while i > -1 and arr[i] == last:
			i -= 1
		if i > -1:
			result += 1
			i = 2 * i - n + 1
	return result
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	print(fun(n, arr))


def main():
	T = int(input())
	for x in range(T):
		n = int(input())
		array = list(map(int, input().split(' ')))
		temp = array[n - 1]
		(steps, chain, i, temp) = (0, 1, n - 2, array[n - 1])
		while i >= 0:
			if array[i] == temp:
				chain += 1
				i -= 1
			else:
				steps += 1
				i -= chain
				chain *= 2
		print(steps)
main()


for _ in range(int(input())):
	n = int(input())
	numbers = list(map(int, input().split()))
	count = 1
	i = n - 2
	o = 0
	last = numbers[-1]
	while i >= 0:
		if numbers[i] == last:
			count += 1
			i -= 1
		else:
			i -= count
			count *= 2
			o += 1
	print(o)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b = b[::-1]
	i = 1
	c = 0
	while i < a:
		if b[0] != b[i]:
			c += 1
			i = i * 2
		else:
			i += 1
	print(c)


import sys
from math import *
from math import *
from functools import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = n - 1
	c = 0
	m = a[n - 1]
	while i > 0:
		while i > 0 and a[i - 1] == m:
			i -= 1
		if i > 0:
			c += 1
			i = 2 * i - n
	print(c)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	cur = n - 1
	ans = 0
	while cur >= 0:
		while cur >= 0 and a[cur] == a[-1]:
			cur -= 1
		if cur >= 0:
			cur = cur - (n - cur - 1)
			ans += 1
	print(ans)
tst = int(input())
for tt in range(tst):
	solve()


def main():
	test_no = int(input())
	for _ in range(test_no):
		n = int(input())
		elems = [int(elem) for elem in input().split()]
		if len(elems) == 1:
			print(0)
			continue
		count = 0
		i = -2
		val = elems[-1]
		while -i <= len(elems):
			if elems[i] == val:
				i -= 1
			else:
				i += i + 1
				count += 1
		print(count)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	c = 0
	p = a[n - 1]
	i = 1
	j = n - 2
	while j >= 0:
		while j >= 0 and a[j] == p:
			i += 1
			j -= 1
		if j < 0:
			break
		c += 1
		j -= i
		i *= 2
	print(c)


def executeCases():
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		return
	operations = 0
	cur = n - 2
	print(getOperations(n, a, cur, operations))

def getOperations(n, a, cur, operations):
	while cur >= 0 and a[cur] == a[-1]:
		cur -= 1
	if cur == 0:
		return operations + 1
	elif cur < 0:
		return operations
	else:
		operations += 1
		cur -= n - cur - 1
		return getOperations(n, a, cur, operations)
t = int(input())
for i in range(t):
	executeCases()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	index = n - 1
	num = a[n - 1]
	while index >= 0:
		if a[index] == num:
			index -= 1
		else:
			ans += 1
			index -= n - index - 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.reverse()
	check = a[0]
	i = 0
	count = 0
	while i < n - 1:
		if a[i + 1] != check:
			count = count + 1
			i = 2 * i + 1
			continue
		else:
			i = i + 1
	print(count)


def find_min_ops2(n, a):
	num_ops = 0
	a.reverse()
	common = a[0]
	i = 1
	while i < n:
		if a[i] != common:
			num_ops += 1
			i *= 2
		else:
			i += 1
	return num_ops
T = int(input())
for t in range(T):
	n = int(input())
	a = [int(k) for k in input().split()]
	print(find_min_ops2(n, a))


tc = int(input())
for tt in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = arr[::-1]
	x = 1
	ans = 0
	while x < n:
		if arr[x] != arr[0]:
			x *= 2
			ans += 1
		else:
			x += 1
	print(ans)


tst = int(input())
for i in range(tst):
	n = int(input())
	a = list(reversed(list(map(int, input().split()))))
	ans = 0
	i = 1
	while i < n:
		if a[i] == a[0]:
			i += 1
		else:
			ans += 1
			i *= 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	v = lis[-1]
	k = n - 2
	a = 0
	while k >= 0:
		if lis[k] == v:
			k -= 1
		else:
			a += 1
			k -= n - k - 1
	print(a)


def solve(A):
	ret = 0
	suf = 1
	val = A[-1]
	p = len(A) - 2
	while p >= 0:
		if A[p] != val:
			ret += 1
			suf *= 2
			p = len(A) - suf - 1
		else:
			suf += 1
			p -= 1
	return ret
t = int(input())
for _ in range(t):
	_ = input()
	A = [int(x) for x in input().split()]
	print(solve(A))


t = int(input())
for i in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	num.reverse()
	idx = 0
	cnt = 0
	same = num[0]
	while idx < n - 1:
		if num[idx + 1] == same:
			idx += 1
		else:
			idx += idx + 1
			cnt += 1
	print(cnt)


for x in range(int(input())):
	(_, a) = (input(), input().split()[::-1])
	t = 0
	i = 1
	while i < len(a):
		if a[i] == a[0]:
			i += 1
		else:
			t += 1
			i *= 2
	print(t)


case = int(input())
for i in range(case):
	n = int(input())
	ll = list(map(int, input().split()))
	ss = ll[-1]
	t = n - 2
	count = 0
	while t >= 0:
		if ll[t] != ss:
			count += 1
			t -= n - t - 1
		else:
			t -= 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(i, ans, final) = (n - 1, 0, a[-1])
	while i >= 0:
		if a[i] == final:
			i -= 1
		else:
			ans += 1
			k = n - 1 - i
			i -= k
	print(ans)


for t in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	i = n - 1
	target = arr[n - 1]
	count = 0
	while i >= 0:
		if arr[i] == target:
			i -= 1
		else:
			i -= n - i - 1
			count += 1
	print(count)


def fun():
	n = int(input())
	arr = list(map(int, input().split()))
	k = arr.pop()
	count = 0
	i = 1
	while arr:
		if arr[-1] == k:
			arr.pop()
			i += 1
		else:
			arr = arr[:-i]
			count += 1
			i = i + i
	return count

def main():
	for _ in range(int(input())):
		print(fun())
main()


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	el = a[-1]
	count = 0
	pos = len(a) - 2
	while pos >= 0:
		if a[pos] == el:
			pos = pos - 1
		else:
			k = len(a) - (pos + 1)
			pos = pos - k
			count = count + 1
	return count
t = int(input())
for tc in range(t):
	print(solve())


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def solve():
	n = int(input())
	a = intlist()
	l = a[-1]
	seq = 1
	ans = 0
	i = n - 2
	while i != -1:
		if a[i] == l:
			seq += 1
			i = i - 1
		elif i - seq >= 0:
			i = i - seq
			seq = seq * 2
			ans += 1
		else:
			ans += 1
			break
	return ans
t = input()
for tt in range(int(t)):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = 0
	i = n - 2
	lastSame = n - 1
	while i > -1:
		if a[i] != a[n - 1]:
			ans += 1
			lastSame = n - 2 * (n - lastSame)
			i = lastSame - 1
		else:
			lastSame = i
			i -= 1
	print(ans)


def solve(a, n):
	res = 0
	v = a[int(n) - 1]
	length = 1
	j = int(n) - 1
	j -= 1
	while j >= 0:
		while j >= 0 and a[j] == v:
			length += 1
			j -= 1
		if j < 0:
			break
		res += 1
		j -= length
		length *= 2
	return res
t = int(input())
for i in range(0, t):
	n = input()
	a = list(map(int, input().split()))
	print(solve(a, n))


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = n - 1
	ans = 0
	while x > 0:
		while x > 0 and a[x - 1] == a[-1]:
			x -= 1
		if x == 0 and a[x] == a[-1]:
			break
		if x >= 0:
			x -= n - x
			ans += 1
	print(ans)