For a collection of integers $S$, define $\operatorname{mex}(S)$ as the smallest non-negative integer that does not appear in $S$.

NIT, the cleaver, decides to destroy the universe. He is not so powerful as Thanos, so he can only destroy the universe by snapping his fingers several times.

The universe can be represented as a 1-indexed array $a$ of length $n$. When NIT snaps his fingers, he does the following operation on the array:

He selects positive integers $l$ and $r$ such that $1\le l\le r\le n$. Let $w=\operatorname{mex}(\{a_l,a_{l+1},\dots,a_r\})$. Then, for all $l\le i\le r$, set $a_i$ to $w$.

We say the universe is destroyed if and only if for all $1\le i\le n$, $a_i=0$ holds.

Find the minimum number of times NIT needs to snap his fingers to destroy the universe. That is, find the minimum number of operations NIT needs to perform to make all elements in the array equal to $0$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1\le n\le 10^5$).

The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($0\le a_i\le 10^9$).

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


-----Output-----

For each test case, print one integer — the answer to the problem.


-----Examples-----

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


-----Note-----

In the first test case, we do $0$ operations and all elements in the array are already equal to $0$.

In the second test case, one optimal way is doing the operation with $l=2$, $r=5$.

In the third test case, one optimal way is doing the operation twice, respectively with $l=4$, $r=4$ and $l=2$, $r=6$.

In the fourth test case, one optimal way is doing the operation with $l=1$, $r=1$.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms


Solutions:
for s in [*open(0)][2::2]:
	print(min(2, len(''.join((' *'[x > '0'] for x in s.split())).split())))


for s in [*open(0)][2::2]:
	print(len(''.join((' *'[x > '0'] for x in s.split())).split(None, 1)))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 0 not in a:
		print(1)
	else:
		check = 0
		block = 0
		for i in range(len(a)):
			if a[i] != 0:
				if check == 0:
					block += 1
					check = 1
					if block == 2:
						break
			else:
				check = 0
		print(block)


for srg in [*open(0)][2::2]:
	print(len(''.join((' *'[d > '0'] for d in srg.split())).split(None, 1)))


t = int(input())
ans = []
for e in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if all(map(lambda x: x == 0, a)):
		ans.append(0)
	elif not 0 in a:
		ans.append(1)
	else:
		(c1, c2) = (0, 0)
		for e in a:
			if e == 0:
				c1 += 1
			else:
				break
		a.reverse()
		for e in a:
			if e == 0:
				c2 += 1
			else:
				break
		a.reverse()
		if c2 == 0:
			c2 = -n
		if 0 in a[c1:-c2]:
			ans.append(2)
		else:
			ans.append(1)
print('\n'.join(map(str, 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())

def NIT_destroys_universe(n, a):
	non_zero_segment = 0
	on_non_zero_segment = False
	for i in a:
		if i > 0 and (not on_non_zero_segment):
			non_zero_segment += 1
			on_non_zero_segment = True
		elif i == 0 and on_non_zero_segment:
			on_non_zero_segment = False
		if non_zero_segment >= 2:
			break
	return non_zero_segment if non_zero_segment < 2 else 2
tests = inp()
for test in range(tests):
	n = inp()
	a = inlt()
	print(NIT_destroys_universe(n, a))


res = []
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	s = False
	for e in a:
		if e != 0 and (not s):
			c += 1
			s = True
		elif e == 0:
			s = False
	if c == 0:
		res.append(0)
	elif c == 1:
		res.append(1)
	else:
		res.append(2)
for e in res:
	print(e)


import sys

def main(a, n):
	i = 0
	res = 0
	while i < n and a[i] == 0:
		i += 1
	while i < n:
		res += 1
		while i < n and a[i] != 0:
			i += 1
		while i < n and a[i] == 0:
			i += 1
	return 2 if res > 2 else res
res = []
num = int(sys.stdin.readline())
for i in range(num):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	res.append(main(a, n))
print(*res, sep='\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	universe = list(map(int, input().split()))
	answer = 0
	cur_num = 0
	for num in universe:
		if answer >= 2:
			print(answer)
			break
		if cur_num == 0 and num != 0:
			answer += 1
			cur_num = num
		elif num == 0:
			cur_num = 0
	else:
		print(answer)


x = int(input())
odg = []
for x in range(0, x):
	n = int(input())
	l = input()
	l = ' ' + l
	l = l.split(' 0')
	l = list(filter(lambda a: a != '' and a != ' ', l))
	if len(l) <= 1:
		odg.append(len(l))
	else:
		odg.append(2)
for e in odg:
	print(e)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	for i in range(1, n):
		if arr[i] > 0 and arr[i - 1] == 0:
			cnt += 1
	cnt += 1 if arr[0] > 0 else 0
	return min(cnt, 2)
for _ in range(int(input())):
	print(solve())


from os import error
import sys
input = sys.stdin.readline
DEBUG = False

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

def solve():
	n = inp()
	datum = inlt()
	ans = 0
	datum.insert(0, 0)
	datum.append(0)
	for (i, v) in enumerate(datum):
		if i == 0:
			continue
		if datum[i - 1] == 0 and datum[i] != 0:
			ans += 1
	return min(ans, 2)
q = inp()
for t in range(q):
	ans = solve()
	print(ans)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = 0
	r = 0
	for x in map(int, inp().split()):
		if x == 0:
			if a == 1:
				r += 1
				a = 0
		else:
			a = 1
	print(min(r + a, 2))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
zz = not __debug__
if not zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = int(input())
for i in range(n):
	l = int(input())
	a = [int(i) for i in input().split()]
	count = 0
	i = 0
	while i < l:
		if a[i] == 0:
			i += 1
			continue
		else:
			while i < l and a[i] != 0:
				i += 1
			count += 1
			continue
	if count <= 1:
		print(count)
	else:
		print(2)


t = int(input())

def find_subsets_greater_than_zero(s: list):
	count = 0
	active = False
	for i in range(len(s)):
		if s[i] > 0:
			if not active:
				count += 1
				active = True
		elif active:
			active = False
	return count
l = []
results = []
for i in range(t):
	n = int(input())
	universe = [int(x) for x in input().split(' ')]
	subsets_of_non_zeros = find_subsets_greater_than_zero(universe)
	if subsets_of_non_zeros < 2:
		results.append(subsets_of_non_zeros)
	else:
		results.append(2)
for res in results:
	print(res)


for a in [*open(0)][2::2]:
	a = [*map(int, a.split())]
	z = 0
	ans = 0
	for i in a:
		if i != 0:
			z += 1
		else:
			ans += z > 0
			z = 0
	ans += z > 0
	print(min(ans, 2))


for _ in range(int(input())):
	a = int(input())
	l = input().split(' 0 ')
	x = 0
	for i in l:
		if i == '0' or i == '0 0':
			pass
		else:
			x += 1
	if x > 2:
		print(2)
	else:
		print(x)


for _ in range(int(input())):
	input()
	a = input().split()
	prev0 = True
	cnt = 0
	for x in a:
		if x == '0':
			if not prev0:
				prev0 = True
		elif prev0:
			prev0 = False
			cnt += 1
	print(min(cnt, 2))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	L = 0
	for i in range(N):
		if A[i] != 0:
			break
		L += 1
	R = N
	for i in range(N - 1, -1, -1):
		R -= 1
		if A[i] != 0:
			break
	if N == 1 and A[0] != 0:
		print(1)
	elif L > R:
		print(0)
	else:
		ans = 1
		for i in range(L, R):
			if A[i] == 0 and A[i + 1] != 0:
				ans += 1
		print(min(ans, 2))


t = int(input())
for _ in range(t):
	n = [int(x) for x in input()]
	arr = input().split()
	ans = 0
	is0 = True
	for a in arr:
		if a == '0':
			is0 = True
		else:
			if is0:
				ans += 1
			is0 = False
		if ans >= 2:
			break
	print(ans)


fptr = open(0)
for _ in range(int(next(fptr))):
	n = int(next(fptr))
	a = list(map(int, next(fptr).split()))
	l = r = -1
	count = temp = 0
	for i in range(n):
		if l == -1 and a[i] != 0:
			l = i
		elif a[i] != 0:
			r = i
			count += temp
			temp = 0
		elif a[i] == 0 and l != -1:
			temp += 1
	if count:
		print(2)
	elif l != -1:
		print(1)
	else:
		print(0)


ans = []
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	i = 0
	while i < n:
		if a[i] != 0:
			j = i
			x += 1
			while j < n:
				if a[j] == 0:
					break
				j += 1
				i += 1
		else:
			i += 1
	ans.append(x)
for i in ans:
	if i == 0:
		print(i)
	elif i == 1:
		print(i)
	else:
		print('2')


n = int(input())
a = []
for i in range(n):
	x = int(input())
	k = 0
	kolnol = 0
	s = list(map(int, input().split()))
	nol = s.count(0)
	if nol == len(s):
		a.append(0)
	elif nol == 0:
		a.append(1)
	else:
		for j in range(len(s) - 1):
			if s[j] != 0 and s[j + 1] == 0:
				if kolnol + (len(s) - 1 - j) == nol:
					a.append(1)
					k = -1
				else:
					a.append(2)
					k = -1
				break
			if s[j] == 0:
				kolnol += 1
		if k == 0:
			a.append(1)
for i in a:
	print(i)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	n = I()
	arr = L()
	cnt = 0
	i = 0
	while i < n:
		if arr[i] == 0:
			i += 1
		else:
			cnt += 1
			while i < n and arr[i] != 0:
				i += 1
	print(min(cnt, 2))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	c1 = 0
	c = l.count(0)
	if n == 1:
		if l[0] == 0:
			pr(0)
		else:
			pr(1)
	else:
		k = l.count(0)
		if k == n:
			pr(0)
		else:
			i = 0
			j = n - 1
			while i <= j:
				if l[i] != 0 and l[j] != 0:
					break
				elif l[i] == 0 and l[j] != 0:
					i += 1
					c -= 1
				elif l[i] != 0 and l[j] == 0:
					j -= 1
					c -= 1
				elif l[i] == 0 and l[j] == 0:
					i += 1
					j -= 1
					c -= 2
			if c > 0:
				pr(2)
			else:
				pr(1)


for i in range(int(input())):
	n = input()
	c = 0
	ans = 0
	for i in input().split():
		if i == '0':
			if c:
				ans += 1
			c = 0
		else:
			c += 1
	if c:
		ans += 1
	print(min(ans, 2))


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	i = 0
	j = n - 1
	while True:
		if i == n or j == -1:
			break
		if a[i] == 0:
			i += 1
			if a[j] == 0:
				j -= 1
		elif a[j] == 0:
			j -= 1
			if a[i] == 0:
				i += 1
		else:
			break
	if sum(a) == 0:
		ans.append(0)
	else:
		zero = 0
		for j in a[i:j + 1]:
			if j == 0:
				zero = 1
				break
		if zero == 0:
			ans.append(1)
		else:
			ans.append(2)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(input().split())
	Num_Zero = arr.count('0')
	Num_Non_Zero = n - Num_Zero
	Cont_Non_Zero = 0
	if Num_Non_Zero == 0:
		print(0)
	else:
		Cont_Non_Zero = 0
		i = 0
		while i < n:
			if arr[i] != '0':
				while i < n and arr[i] != '0':
					Cont_Non_Zero += 1
					i += 1
				break
			i += 1
		if Cont_Non_Zero == Num_Non_Zero:
			print('1')
		else:
			print(2)


x = int(input())
v = []
b = 1
ans = 0
ans2 = 0
y = []
for _ in range(x):
	n = int(input())
	v = list(map(int, input().split()))
	for i in range(n):
		if v[i] == 0:
			if b == 0:
				ans += 1
				b = 1
		else:
			b = 0
	v = []
	if b == 0:
		ans += 1
		b = 1
	b = 1
	if ans > 2:
		ans = 2
	y.append(ans)
	ans = 0
for i in range(len(y)):
	print(y[i])


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) == 0:
		print(0)
	else:
		d = deque(arr)
		while d and d[0] == 0:
			d.popleft()
		while d and d[-1] == 0:
			d.pop()
		if 0 in d:
			print(2)
		else:
			print(1)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(0) == n:
		print(0)
		return
	prev = -1
	for i in range(len(arr)):
		if arr[i] > 0:
			if prev == -1:
				prev = i
			elif i - prev > 1:
				print(2)
				return
			else:
				prev = i
	print(1)
	return
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if not any(a):
		print(0)
		continue
	while not a[-1]:
		a.pop()
	a.reverse()
	while not a[-1]:
		a.pop()
	print(1 if all(a) else 2)


def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		if sum(a) == 0:
			print(0)
			continue
		i = 0
		while i < n and a[i] == 0:
			i += 1
		while i < n and a[i] != 0:
			i += 1
		while i < n and a[i] == 0:
			i += 1
		if i == n:
			print(1)
			continue
		print(2)
main()


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


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	for i in range(len(arr)):
		if arr[i] != 0 and (i == 0 or arr[i - 1] == 0):
			cnt += 1
	print(min(cnt, 2))
for _ in range(t):
	solve()


t = int(input())

def ndu(arr):
	c = 0
	for i in range(1, len(arr)):
		if arr[i] != 0 and arr[i - 1] == 0:
			c += 1
	if arr[0] != 0:
		c += 1
	if c >= 2:
		return 2
	return c
for i in range(t):
	n = int(input())
	i = [int(i) for i in input().split()]
	ans = ndu(i)
	print(ans)


num_of_cases = int(input())
for _ in range(num_of_cases):
	N = int(input())
	arr = [int(x) for x in input().split(' ')]
	res = 0
	nonzero_start = False
	for num in arr:
		if num != 0:
			if nonzero_start == False:
				nonzero_start = True
		elif nonzero_start == True:
			res += 1
			nonzero_start = False
	if nonzero_start == True:
		res += 1
	if res == 0:
		print(0)
	elif res == 1:
		print(1)
	else:
		print(2)


import types
from functools import lru_cache

def main():
	t = int(input())
	for test in range(t):
		n = int(input())
		a = iin()
		count = 0
		zero = True
		for i in a:
			if i != 0 and zero:
				zero = False
				count += 1
				if count > 2:
					break
			elif i == 0:
				zero = True
		print(min(2, count))

def iin():
	return [int(i) for i in input().split()]
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	f = True
	ans = 0
	done = False
	for i in arr:
		if i > 0:
			if f:
				ans += 1
				f = False
				if ans > 1:
					done = True
		else:
			f = True
		if done:
			break
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = j = 0
	c = 0
	while j < n:
		if a[i] == 0 and i == j:
			i += 1
			j = i
		elif a[j] == 0:
			i = j
			c += 1
		else:
			j += 1
	if a[-1] != 0:
		c += 1
	if c > 1:
		c = 2
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if not any(a):
		print(0)
	else:
		(c1, c2) = (0, 0)
		for e in a:
			if e == 0:
				c1 += 1
			else:
				break
		a.reverse()
		for e in a:
			if e == 0:
				c2 += 1
			else:
				break
		a.reverse()
		if c2 == 0:
			c2 = -n
		if 0 in a[c1:-c2]:
			print(2)
		else:
			print(1)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	cnt = 0
	for i in range(n):
		if a[cnt] != 0:
			ans = ans + 1
			while a[cnt] != 0:
				cnt = cnt + 1
				if cnt == n:
					break
		cnt = cnt + 1
		if cnt >= n:
			break
	ans = min(ans, 2)
	print(ans)

def main():
	for _ in range(int(input())):
		solve()
main()


def input_n():
	return int(input())

def input_n_m():
	return (int(i) for i in input().split())

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

def input_s():
	return ''.join(input().split())

def solve(nums):
	(group, pre) = (0, 0)
	for n in nums:
		if n > 0 and pre == 0:
			group += 1
		pre = n
	return {0: 0, 1: 1}.get(group, 2)
rows = input_n()
for _ in range(rows):
	n = input_n()
	nums = input_nums()
	print(solve(nums))


import math
t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	ans = 2
	if a.count(0) == n:
		ans = 0
	else:
		i = 0
		j = n - 1
		x = a.count(0)
		while a[i] == 0:
			i += 1
			x -= 1
		while a[j] == 0:
			j -= 1
			x -= 1
		if x == 0:
			ans = 1
		else:
			ans = 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	flag = 0
	if a == [0] * n:
		print(0)
		continue
	else:
		ans = 1
		for num in a:
			if cnt >= 2:
				ans = 2
				break
			if num == 0:
				flag = 0
			elif flag == 0:
				cnt = cnt + 1
				flag = 1
		if cnt >= 2:
			ans = 2
		print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	if l[0] != 0:
		ans += 1
	for i in range(n - 1):
		if l[i + 1] != 0 and l[i] == 0:
			ans += 1
	print(min(ans, 2))


for i in range(int(input())):
	n = int(input())
	c = [int(j) for j in input().split()]
	if sum(c) == 0:
		print(0)
	else:
		u = 0
		while c[u] == 0:
			u += 1
		while c[-1] == 0:
			c.pop()
		print([1, 2][0 in c[u:]])


T = int(input())
for i in range(T):
	n = input()
	ans = 0
	lst = list(map(int, input().split())) + [0]
	prev = 0
	for x in lst:
		if not x and prev:
			ans = ans + 1
		prev = x
	print(min(2, ans))


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	zero = 0
	for z in arr:
		if z == 0:
			zero += 1
	if zero == n:
		return 0
	if zero == 0:
		return 1
	i = 0
	while i < n:
		if arr[i] != 0:
			break
		i += 1
	j = n - 1
	while j > 0:
		if arr[j] != 0:
			break
		j -= 1
	aux = arr[i:j + 1]
	for z in aux:
		if z == 0:
			return 2
	return 1
for _ in range(int(input())):
	print(main())


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


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	j = 0
	k = 0
	for r in range(n):
		if a[r] != 0:
			k += 1
		elif k != 0:
			j += 1
			k = 0
	if k != 0:
		j += 1
	if j > 2:
		print(2)
	else:
		print(j)


T = int(input())
while T:
	T -= 1
	N = int(input())
	arr = list(map(int, input().split()))
	i = 0
	c = 0
	d = 0
	while i < N and arr[i] == 0:
		i += 1
	if i == N:
		print(0)
		continue
	j = N - 1
	while j >= 0 and arr[j] == 0:
		j -= 1
	while i < j + 1:
		if arr[i] == 0:
			c += 1
			while i < N and arr[i] == 0:
				i += 1
		else:
			d = 1
			i += 1
	if d == 0:
		print(0)
	elif c == 0:
		print(1)
	else:
		print(2)


import math
t = int(input())
while t:
	t -= 1
	h = input()
	a = int(h)
	lis = input().split()
	lis = [int(x) for x in lis]
	if max(lis) == 0:
		print(0)
		continue
	if a == 1:
		print(1)
		continue
	fir = 0
	if lis[0] != 0 and lis[1] == 0:
		fir += 1
	lis[0] = 0
	for ind in range(1, a):
		if lis[ind] != 0 and lis[ind - 1] == 0:
			fir += 1
		if fir == 2:
			break
	print(fir)


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


def solve(A):
	ans = 0
	prev = -1
	for i in A:
		if prev > 0 and i > 0:
			continue
		if prev > 0 and i == 0:
			ans += 1
		prev = i
	if prev > 0:
		ans += 1
	return ans if ans < 2 else 2

def read():
	A = []
	line = input()
	n = int(line)
	line = input()
	ss = line.split(' ')
	for s in ss:
		A.append(int(s))
	return A

def main():
	n = int(input())
	for _ in range(n):
		A = read()
		print(solve(A))
	pass
main()


def meow(l, n):
	i = 0
	count = 0
	mem = 0
	while i < n - 1:
		if l[i] != 0:
			if l[i + 1] == 0:
				j = 0
				while j < n - i - 1:
					if l[i + 1 + j] != 0:
						return 2
					j = j + 1
				return 1
		i = i + 1
	if l[n - 1] == 0:
		return 0
	else:
		return 1
tt = 0
t = int(input())
while tt < t:
	nu = int(input())
	ok = list(map(int, input().split()))
	print(meow(ok, nu))
	tt = tt + 1


tests = int(input())
for _ in range(tests):
	n = int(input())
	v = list(map(int, input().split()))
	prev = -1
	ans = 0
	breakk = False
	for (i, x) in enumerate(v):
		if i == 0:
			if x != 0:
				ans += 1
			prev = x
			continue
		if x != 0 and prev == 0:
			ans += 1
			if ans == 2:
				print(ans)
				breakk = True
				break
			prev = x
			continue
		prev = x
	if not breakk:
		print(ans)


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	mode = 0
	count = 0
	for i in s:
		if i:
			if mode == 0:
				count += 1
				mode = 1
		else:
			mode = 0
	print(min(count, 2))


n = int(input())
for _ in range(n):
	long = int(input())
	l = list(map(int, input().split()))
	ind = 0
	for i in range(long):
		if l[i] != 0:
			ind = 1
			break
	if ind == 0:
		print(0)
	else:
		x = i
		for i in range(long - 1, -1, -1):
			if l[i] != 0:
				break
		y = i
		if 0 not in l[x:y + 1]:
			print(1)
		else:
			print(2)


def func():
	n = int(input())
	arr = list(map(int, input().split()))
	l = 0
	c = 0
	if arr[0] != 0:
		c += 1
	while l < n - 1:
		if arr[l] == 0 and arr[l + 1] != 0:
			c += 1
		l += 1
	if c >= 2:
		print(2)
	else:
		print(c)
tc = int(input())
while tc > 0:
	func()
	tc -= 1


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	if li.count(0) == n:
		print(0)
		continue
	if 0 not in li:
		print(1)
		continue
	c = d = -1
	for i in range(n):
		if li[i] != 0:
			if c == -1:
				c = i
			d = i
	if 0 not in li[c:d + 1]:
		print(1)
		continue
	print(2)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l == [0] * n:
		print(0)
	else:
		groups = 0
		for j in range(n):
			if l[j] > 0 and (j == 0 or l[j - 1] == 0):
				groups += 1
		if groups >= 2:
			print(2)
		else:
			print(1)


import sys

def main():
	t = int(input())
	for i in range(t):
		solve()

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	i = 0
	swich = False
	while i < n:
		if a[i] != 0 and (not swich):
			swich = True
			c += 1
			if c >= 2:
				break
		elif a[i] == 0 and swich:
			swich = False
		i += 1
	print(c)
main()


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(first_done, last_done) = (False, False)
	first_nz = 0
	last_nz = n - 1
	for i in range(n):
		if first_done and last_done:
			break
		else:
			if a[i] != 0 and first_done == False:
				first_nz = i
				first_done = True
			if a[n - i - 1] != 0 and last_done == False:
				last_nz = n - i - 1
				last_done = True
	if (first_nz == 0 and a[first_nz] == 0) and (last_nz == n - 1 and a[last_nz] == 0):
		print('0')
		continue
	if 0 in a[first_nz:last_nz]:
		print('2')
		continue
	else:
		print('1')
		continue


t = int(input())
for i in range(t):
	s = input()
	n = int(s.split()[0])
	arr = input().split()
	arr = list(map(int, arr))
	lnz = n
	rnz = -1
	for i in range(n):
		if arr[i] != 0:
			lnz = i
			break
	if lnz == n:
		print(0)
		continue
	for i in range(n - 1, -1, -1):
		if arr[i] != 0:
			rnz = i
			break
	res = 1
	for i in range(lnz, rnz + 1):
		if arr[i] == 0:
			res = 2
			break
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	z = 0
	for i in arr:
		if i == 0:
			z += 1
	if z == n:
		print(0)
	elif z == 0:
		print(1)
	else:
		s = 0
		for i in range(n):
			if arr[i] == 0:
				continue
			if i == n - 1 or arr[i + 1] == 0:
				s += 1
		if s == 1:
			print(1)
		else:
			print(2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	a = 0
	for i in range(n):
		if l[i] != 0:
			c += 1
		elif c != 0:
			a += 1
			c = 0
	if c != 0:
		a += 1
	if a > 2:
		a = 2
	print(a)


for t in range(int(input())):
	input()
	s = [0] + [*map(int, input().split())]
	c = 0
	for i in range(len(s) - 1):
		if s[i] == 0 and s[i + 1] != 0:
			c += 1
	print(min(c, 2))


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if len(set(a)) == 1 and a[0] == 0:
		print('0\n')
		continue
	a = deque(a)
	while a and a[-1] == 0:
		a.pop()
	while a and a[0] == 0:
		a.popleft()
	if 0 in a:
		print('2\n')
	else:
		print('1\n')


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
t = num_inp()
for _ in range(t):
	n = num_inp()
	l = arr_inp()
	count = l.count(0)
	if count == n:
		print(0)
		continue
	count = 0
	ind = -1
	for i in range(n):
		if l[i] == 0:
			if i - ind > 1:
				count += 1
			ind = i
	if n - ind >= 2:
		count += 1
	if count >= 2:
		print(2)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split())) + [0]
	c = 0
	pre = 0
	for i in A:
		if i == 0 and pre != 0:
			c += 1
		pre = i
	print(min(c, 2))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	x = 1 if s[0] > 0 else 0
	for i in range(1, n):
		if s[i] > 0 and s[i - 1] == 0:
			x += 1
		if x >= 2:
			break
	print(x)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(set(a)) == 1:
		if a[0] == 0:
			print(0)
		else:
			print(1)
	else:
		n += 1
		a.append(0)
		nit = 0
		for i in range(n - 1):
			if a[i] != 0 and a[i + 1] == 0:
				nit += 1
		if nit == 1:
			print(1)
		else:
			print(2)


def destroy_count(a, n):
	count = 0
	if a[0] != 0:
		count += 1
	for i in range(1, n):
		if a[i - 1] == 0 and a[i] != 0:
			count += 1
			if count > 2:
				return 2
	return count
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().rstrip().split()))
	ans = destroy_count(a, n)
	print(ans)


def solve(a, n):
	if a.count(0) == n:
		print(0)
		return
	(l, r) = (0, n - 1)
	while a[l] == 0:
		l += 1
	while a[r] == 0:
		r -= 1
	for i in range(l, r + 1):
		if a[i] == 0:
			print(2)
			return
	print(1)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	solve(a, n)


for _ in range(int(input())):
	n = int(input())
	arr = (*map(int, input().split()),)
	count = 0
	last = 0
	for num in arr:
		if num == 0:
			if last != 0:
				count += 1
		last = num
	if last != 0:
		count += 1
	print(min(count, 2))


for h in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if x.count(0) == n:
		print(0)
	else:
		c = 0
		if x[0] != 0:
			c += 1
		for i in range(1, n):
			if x[i - 1] == 0 and x[i] != 0:
				c += 1
		if c == 1:
			print(1)
		else:
			print(2)


from collections import deque
t = int(input())
for elem in range(t):
	n = int(input())
	d = deque([int(el) for el in input().split()])
	c = d.count(0)
	if c == n:
		print(0)
	elif c == 0:
		print(1)
	else:
		while d[-1] == 0:
			d.pop()
			c -= 1
		while d[0] == 0:
			d.popleft()
			c -= 1
		if c == 0:
			print(1)
		else:
			print(2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(0)
	if c == n:
		print(0)
	elif c == 0:
		print(1)
	else:
		k = 0
		for i in range(n):
			if i == 0:
				if a[i] != 0:
					k += 1
			elif a[i] != 0 and a[i - 1] == 0:
				k += 1
		if k < 2:
			print(1)
		else:
			print(2)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	i = 0
	ar = arr.copy()
	if 1 == 2:
		a = 0
	else:
		ans = 0
		i = 0
		while i < n:
			if ar[i] != 0:
				ans += 1
				while i < n and ar[i] != 0:
					i += 1
			i += 1
		ans = min(2, ans)
		print(ans)


t = int(input())
for x in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	count = 0
	a = []
	for el in arr:
		if el != 0:
			a.append(el)
		elif len(a) > 0:
			count += 1
			a = []
	if len(a) > 0:
		count += 1
	print(min(2, count))


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

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	count = A.count(0)
	if count == n:
		print(0)
		return
	flag = 0
	ok = 0
	k = 0
	for i in range(n):
		if A[i] > 0 and flag == 0 and (ok < 1):
			flag = 1
			ok += 1
		elif A[i] > 0 and flag == 1:
			k += 1
			continue
		elif A[i] == 0:
			flag = 0
		else:
			break
		k += 1
	if k == n:
		print(1)
	else:
		print(2)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	l = [int(i) for i in input().split()]
	flag = 0
	c = 0
	a = 0
	for i in l:
		if i == 0:
			if a == 0:
				continue
			else:
				a = 0
				c += 1
		else:
			a += 1
	if a > 0:
		print(min(2, c + 1))
	else:
		print(min(2, c))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == 0 and len(set(a)) == 1:
		print(0)
		return
	arr = [a[0]]
	for i in range(1, n):
		if a[i] == arr[-1]:
			continue
		arr.append(a[i])
	x = arr[1:-1].count(0)
	if x == 0:
		print(1)
	else:
		print(2)
for t in range(int(input())):
	solve()


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(0) == n:
		print(0)
	else:
		l = 0
		r = n - 1
		count = 0
		while arr[l] == 0:
			l += 1
			count += 1
		while arr[r] == 0:
			r -= 1
			count += 1
		if count == arr.count(0):
			print(1)
		else:
			print(2)