You are given a permutation $a$ consisting of $n$ numbers $1$, $2$, ..., $n$ (a permutation is an array in which each element from $1$ to $n$ occurs exactly once).

You can perform the following operation: choose some subarray (contiguous subsegment) of $a$ and rearrange the elements in it in any way you want. But this operation cannot be applied to the whole array.

For example, if $a = [2, 1, 4, 5, 3]$ and we want to apply the operation to the subarray $a[2, 4]$ (the subarray containing all elements from the $2$-nd to the $4$-th), then after the operation, the array can become $a = [2, 5, 1, 4, 3]$ or, for example, $a = [2, 1, 5, 4, 3]$.

Your task is to calculate the minimum number of operations described above to sort the permutation $a$ in ascending order.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases.

The first line of the test case contains a single integer $n$ ($3 \le n \le 50$) — the number of elements in the permutation.

The second line of the test case contains $n$ distinct integers from $1$ to $n$ — the given permutation $a$.


-----Output-----

For each test case, output a single integer — the minimum number of operations described above to sort the array $a$ in ascending order.


-----Examples-----

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


-----Note-----

In the explanations, $a[i, j]$ defines the subarray of $a$ that starts from the $i$-th element and ends with the $j$-th element.

In the first test case of the example, you can select the subarray $a[2, 3]$ and swap the elements in it.

In the second test case of the example, the permutation is already sorted, so you don't need to apply any operations.

In the third test case of the example, you can select the subarray $a[3, 5]$ and reorder the elements in it so $a$ becomes $[2, 1, 3, 4, 5]$, and then select the subarray $a[1, 2]$ and swap the elements in it, so $a$ becomes $[1, 2, 3, 4, 5]$.

Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if sorted(l) == l:
		print(0)
	elif l[0] == max(l) and l[-1] == min(l):
		print(3)
	elif l[0] == min(l) or l[-1] == max(l):
		print(1)
	else:
		print(2)


import sys
fi = lambda : sys.stdin.readline()
for _ in range(int(fi())):
	n = int(fi())
	l = list(map(int, fi().split()))
	if l == sorted(l):
		print(0)
	elif l[0] == 1 or l[-1] == n:
		print(1)
	elif l[0] == n and l[-1] == 1:
		print(3)
	else:
		print(2)


w = int(input())
for i in range(w):
	k = int(input())
	t = list(map(int, input().split()))
	b = list(t)
	y = list(t)
	y.sort(reverse=True)
	b.sort()
	if b == t:
		print(0)
	elif b[0] == t[0] or b[-1] == t[-1]:
		print(1)
	elif y[0] == t[0] and y[-1] == t[-1]:
		print(3)
	else:
		print(2)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	if sorted(l) == l:
		print(0)
	elif l[0] == 1 or l[n - 1] == n:
		print(1)
	elif l[0] == n and l[n - 1] == 1:
		print(3)
	else:
		print(2)


r = []
for i in range(int(input())):
	b = int(input())
	(*a,) = map(int, input().split())
	if a == sorted(a):
		r += (0,)
	elif a[0] == b and a[-1] == 1:
		r += (3,)
	elif a[0] == 1 or a[-1] == b:
		r += (1,)
	else:
		r += (2,)
[print(i) for i in r]


import sys
from math import *
import builtins
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)

def get_int():
	return int(input())

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

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

def get_tuple_ints():
	return tuple(map(int, input().split()))

def print_iterable(p):
	print(' '.join(map(str, p)))

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

def main():
	a = get_int()
	for i in range(0, a):
		k = get_int()
		res = 0
		arr = get_list_ints()
		if arr == sorted(arr):
			res = 0
		elif arr[0] == 1 or arr[-1] == k:
			res = 1
		elif arr[0] == k and arr[-1] == 1:
			res = 3
		else:
			res = 2
		print(res)
main()


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print(0)
		continue
	if a[0] == 1 or a[-1] == n:
		print(1)
		continue
	if a[-1] == 1 and a[0] == n:
		print(3)
		continue
	print(2)


import math
import sys
input = sys.stdin.readline

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

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = inlt()
	s = l.copy()
	s.sort()
	if s == l:
		print(0)
	elif l[0] == 1 or l[-1] == n:
		print(1)
	elif l[0] == n and l[-1] == 1:
		print(3)
	else:
		print(2)


tests = int(input())

def sortedN(x):
	i = 0
	while i < len(x) - 1:
		if x[i] > x[i + 1]:
			return False
		i += 1
	return True
for i in range(tests):
	size = int(input())
	val = list(map(int, input().split()))
	if size == 0:
		print('0')
	elif sortedN(val):
		print('0')
	elif min(val) == val[0] or max(val) == val[len(val) - 1]:
		print('1')
	elif min(val) == val[len(val) - 1] and max(val) == val[0]:
		print('3')
	else:
		print('2')


for s in [*open(0)][2::2]:
	a = (x, *_, y) = [*map(int, s.split())]
	print((sorted(a) < a) + ((x, y) == ((n := len(a)), 1)) + (x > 1 <= n - y))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a == list(range(1, n + 1)):
		print(0)
	elif a[0] == 1 or a[-1] == n:
		print(1)
	elif a[0] == n and a[-1] == 1:
		print(3)
	else:
		print(2)


import os
import sys
import math
from io import BytesIO, IOBase
from collections import deque, defaultdict, OrderedDict, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, insort, bisect_left
from functools import lru_cache
from itertools import permutations
sys.setrecursionlimit(10 ** 6)

def STRIN():
	return input()

def INTIN():
	return int(input())

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

def LSTR():
	return list(map(str, input().split()))

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

def MSTR():
	return map(str, input().split())

def solve():
	n = INTIN()
	l = list(map(int, input().split()))
	ans = 2
	flag = 0
	if all((l[i] < l[i + 1] for i in range(n - 1))):
		flag = 1
	if flag:
		ans = 0
	elif l[0] == 1 or l[n - 1] == n:
		ans = 1
	elif l[0] == n and l[n - 1] == 1:
		ans = 3
	print(ans)

def main():
	for _ in range(INTIN()):
		solve()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(0, int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	r = list(range(2, n))
	m = not all((i == j for (i, j) in zip(v[1:n], r)))
	print([m + (v[0] != 1 and v[-1] != n), 3][v[0] == n and v[-1] == 1])


import sys
import math

def solve():
	N = int(input())
	A = list(map(int, input().split()))
	B = sorted(A)
	if A == B:
		return 0
	elif A[0] == 1 or A[-1] == N:
		return 1
	elif A[0] == N and A[-1] == 1:
		return 3
	else:
		return 2
T = int(input())
for i in range(T):
	ans = solve()
	print(ans)


from sys import stdin, stdout, stderr

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

def getInt():
	return int(stdin.readline())
for _ in range(getInt()):
	n = getInt()
	ar = list(getInts())
	if sorted(ar) == ar:
		stdout.write('0\n')
	elif ar[0] == 1 or ar[-1] == n:
		stdout.write('1\n')
	elif ar[0] == n and ar[-1] == 1:
		stdout.write('3\n')
	else:
		stdout.write('2\n')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	b = sorted(a)
	if a == b:
		print(0)
	elif a == b[::-1]:
		print(3)
	elif a[0] == 1 or a[-1] == n:
		print(1)
	elif a[0] == n and a[-1] == 1:
		print(3)
	else:
		print(2)


import math

def main():
	t = int(input())
	for _ in range(t):
		print(case())

def case():
	n = int(input())
	a = list(map(int, input().split()))
	if a == sorted(a):
		return 0
	if a[0] == 1 or a[-1] == n:
		return 1
	if a[0] == n and a[-1] == 1:
		return 3
	return 2
main()


tc = int(input())
for i in range(tc):
	x = int(input())
	y = list(map(int, input().split()))
	z = y.copy()
	z.sort()
	if y == z:
		print(0)
	elif y[0] == x and y[-1] == 1:
		print(3)
	elif y[0] == 1 or y[-1] == x:
		print(1)
	else:
		print(2)


for Z in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	a = len(lis)
	if lis == sorted(lis):
		print(0)
	elif lis[0] == 1 or lis[a - 1] == n:
		print(1)
	elif lis[0] == n and lis[a - 1] == 1:
		print(3)
	else:
		print(2)


from sys import stdin, stdout
intn = lambda : int(stdin.readline())
strs = lambda : stdin.readline()[:-1]
lstr = lambda : list(stdin.readline()[:-1])
mint = lambda : map(int, stdin.readline().split())
lint = lambda : list(map(int, stdin.readline().split()))
out = lambda x: stdout.write(str(x) + '\n')
out_ = lambda x: stdout.write(str(x) + ' ')

def main():
	for _ in range(intn()):
		n = intn()
		a = lint()
		if sorted(a) == a:
			out(0)
		elif a[0] == n and a[-1] == 1:
			out(3)
		elif a[0] == 1 or a[-1] == n:
			out(1)
		else:
			out(2)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	f = True
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			f = False
			break
	if f:
		print(0)
	elif arr[0] == 1 or arr[n - 1] == n:
		print(1)
	elif arr[0] == n and arr[n - 1] == 1:
		print(3)
	else:
		print(2)


import math
for testis in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = l.copy()
	p.sort()
	if l == p:
		print(0)
	elif l[0] == n and l[-1] == 1:
		print(3)
	elif l[0] != 1 and l[-1] != n:
		print(2)
	else:
		print(1)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	mini = min(l)
	maxi = max(l)
	ans = 0
	r = l[:]
	r.sort()
	if r == l:
		ans = 0
	elif l[n - 1] == maxi or l[0] == mini:
		ans = 1
	elif l[0] == maxi and l[n - 1] == mini:
		ans = 3
	else:
		ans = 2
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


for kjdj in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [i for i in range(1, n + 1)]
	if a == b:
		print(0)
		continue
	if a[0] == 1 or a[-1] == n:
		print(1)
		continue
	if a[0] == n and a[-1] == 1:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	arr1 = [int(i) for i in input().split()]
	arr2 = sorted(arr1)
	if arr1 == arr2:
		print(0)
	elif arr1[0] == arr2[0] or arr1[-1] == arr2[-1]:
		print(1)
	elif arr1[-1] == arr2[0] and arr1[0] == arr2[-1]:
		print(3)
	else:
		print(2)


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	isSorted = True
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			isSorted = False
			break
	if isSorted:
		print(0)
		return
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	elif arr[-1] == 1 and arr[0] == n:
		print(3)
	else:
		print(2)
for i in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.copy()
	a.sort()
	if l == a:
		print(0)
	elif l[0] == 1 or l[n - 1] == n:
		print(1)
	elif l[0] == n and l[n - 1] == 1:
		print(3)
	else:
		print(2)


import os
import sys
from io import BytesIO, IOBase
import copy

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = [int(x) for x in input().split()]
		z = sorted(a)
		if z == a:
			print(0)
		elif z[0] == a[0] or z[-1] == a[-1]:
			print(1)
		elif z[0] == a[-1] and a[0] == z[-1]:
			print(3)
		else:
			print(2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = sorted(A)
	if A == B:
		print(0)
	elif A[0] == B[0] or A[-1] == B[-1]:
		print(1)
	elif A[0] == B[-1] and A[-1] == B[0]:
		print(3)
	else:
		print(2)


def perm(arr, n):
	if a == sorted(a):
		return 0
	elif a[0] == 1 or a[-1] == n:
		return 1
	elif a[0] == n and a[-1] == 1:
		return 3
	else:
		return 2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(perm(a, n))


from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math
import threading
import sys
import time

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

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

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

def solve():
	n = get_int()
	ls = get_list()
	sorted_ls = list(sorted(ls))
	if ls == sorted_ls:
		print(0)
	else:
		mini = sorted_ls[0]
		maxi = sorted_ls[-1]
		if mini == ls[0]:
			print(1)
		elif maxi == ls[-1]:
			print(1)
		else:
			c = 0
			if mini == ls[-1]:
				c += 1
			if maxi == ls[0]:
				c += 1
			if c == 2:
				print(3)
			else:
				print(2)
testcases = True
if testcases:
	t = get_int()
	for _ in range(t):
		solve()
else:
	solve()


t = int(input())
for loop in range(0, t):
	size = int(input())
	x = input()
	a = x.split(' ')
	b = x.split(' ')
	a = [int(i) for i in a]
	b = [int(i) for i in b]
	b.sort()
	if a[-1] == b[0] and a[0] == b[-1]:
		print(3)
		continue
	if a[0] != b[0] and a[-1] != b[-1]:
		print(2)
		continue
	for i in range(0, len(a)):
		if a[i] != b[i]:
			break
	else:
		print(0)
		continue
	print(1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	flag = True
	for i in range(0, n):
		if a[i] != i + 1:
			flag = False
			break
	if flag:
		print('0')
	elif a[0] == 1 or a[n - 1] == n:
		print('1')
	elif a[0] == n and a[n - 1] == 1:
		print('3')
	else:
		print('2')


from collections import Counter
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	sorted_arr = sorted(arr)
	if arr == sorted_arr:
		return 0
	elif arr[0] == sorted_arr[0] or arr[-1] == sorted_arr[-1]:
		return 1
	elif arr[0] == sorted_arr[-1] and arr[-1] == sorted_arr[0]:
		return 3
	else:
		return 2
for _ in range(int(input())):
	print(solve())


t = int(input())

def mini(n, L):
	if n == 1:
		return 0
	if n == 2:
		if L[0] == 1:
			return 0
		else:
			return 1
	if L[0] == 1:
		for i in range(n):
			if L[i] != i + 1:
				return 1
		return 0
	elif L[0] != n:
		if L[-1] == n:
			return 1
		else:
			return 2
	elif L[-1] != 1:
		return 2
	else:
		return 3
for _ in range(t):
	n = int(input())
	L = [int(x) for x in input().split()]
	print(mini(n, L))


from sys import stdin, stdout
input = stdin.readline

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

def ii():
	return int(input())

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

def ins():
	return input()[:-1]

def check(lis):
	for i in range(1, len(lis)):
		if lis[i] <= lis[i - 1]:
			return False
	return True
for _ in range(ii()):
	n = ii()
	lis = il()
	if check(lis):
		print(0)
	elif lis[0] == 1 or lis[-1] == n:
		print(1)
	elif lis[0] == n and lis[-1] == 1:
		print(3)
	else:
		print(2)


tc = int(input())
for _ in range(tc):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	if l[0] == n and l[-1] == 1:
		print(3)
		continue
	if l[0] == 1 and l[-1] == n:
		if n <= 3:
			print(cnt)
			continue
		for i in range(1, n - 2):
			if l[i] > l[i + 1]:
				cnt += 1
				break
		print(cnt)
		continue
	if l[0] != 1:
		cnt += 1
	if l[-1] != n:
		cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if arr[i] != i + 1:
			ans = 1
			break
	if ans == 0:
		print(0)
	elif arr[0] == n and arr[n - 1] == 1:
		print(3)
	elif arr[0] == 1 or arr[n - 1] == n:
		print(1)
	else:
		print(2)


for p in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a == sorted(a):
		print(0)
	elif a[0] == 1 and a[-1] == n:
		print(1)
	elif a[0] == 1:
		print(1)
	elif a[-1] == n:
		print(1)
	elif a[0] == n and a[-1] == 1:
		print(3)
	else:
		print(2)


import os
import sys
from io import BytesIO, IOBase
from typing import List, Dict, Tuple

def main():
	t: int = int(sys.stdin.readline())
	for t in range(t):
		n: int = int(sys.stdin.readline())
		a: List[int] = list(map(int, sys.stdin.readline().split()))
		asort = sorted(a)
		if asort == a:
			print(0)
		elif a[0] == 1 or a[-1] == n:
			print(1)
		elif a[0] == n and a[-1] == 1:
			print(3)
		else:
			print(2)
sys.setrecursionlimit(10 ** 6)
main()


import sys
sys.setrecursionlimit(10 ** 6)

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

def LI():
	return list(map(int, sys.stdin.readline().split()))
INF = float('inf')
MOD = 10 ** 9 + 7

def solve():
	t: int = II()
	for t in range(t):
		n = II()
		a = LI()
		asort = sorted(a)
		if asort == a:
			print(0)
		elif a[0] == 1 or a[-1] == n:
			print(1)
		elif a[0] == n and a[-1] == 1:
			print(3)
		else:
			print(2)
	return
solve()


t = int(input())
import math
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	if a == b:
		print(0)
		continue
	if a[0] == 1:
		print(1)
		continue
	if a[-1] == n:
		print(1)
		continue
	if a[0] == n and a[-1] == 1:
		print(3)
		continue
	print(2)


import math
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = True
	for i in range(1, n + 1):
		if arr[i - 1] != i:
			flag = False
			break
	if flag:
		print(0)
		continue
	if arr[0] == 1 or arr[-1] == n:
		print(1)
		continue
	if arr[0] == n and arr[-1] == 1:
		print(3)
		continue
	print(2)


for run in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	cpy = lst.copy()
	cpy.sort()
	if lst == cpy:
		print(0)
	elif lst[0] == 1 or lst[-1] == n:
		print(1)
	elif lst[0] == n and lst[-1] == 1:
		print(3)
	else:
		print(2)


n = int(input().strip())
for _ in range(n):
	l = int(input().strip())
	a = list(map(int, input().strip().split()))
	w = [i for i in range(1, l + 1)]
	if a == w:
		print(0)
	elif a[0] == l and a[l - 1] == 1:
		print(3)
	elif a[0] == 1 or a[l - 1] == l:
		print(1)
	else:
		print(2)


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


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a
	b = sorted(b)
	count = 2
	if b == a:
		count = 0
	elif a[0] == 1 or a[n - 1] == n:
		count = 1
	elif a[0] == n and a[n - 1] == 1:
		count = 3
	print(count)


import math, re, bisect
from collections import Counter, deque
ReadStr = lambda : input()
ReadIntList = lambda : list(map(int, input().split()))
ReadStrList = lambda : list(map(str, input().split()))
ReadInt = lambda : int(input())
ReadMultipleValues = lambda : map(int, input().split())
ReadMultipleValuesStr = lambda : map(str, input().split())
for _ in range(ReadInt()):
	n = ReadInt()
	Array = ReadIntList()
	maxx = Array.index(max(Array))
	minn = Array.index(min(Array))
	if sorted(Array) == Array:
		print(0)
	elif maxx == n - 1 and minn != 0:
		print(1)
	elif minn == 0 and maxx != n - 1:
		print(1)
	elif minn == 0 and maxx == n - 1 and (sorted(Array) != Array):
		print(1)
	elif maxx == 0 and minn == n - 1:
		print(3)
	elif minn != 0 and maxx != n - 1:
		print(2)


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	je = True
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			je = False
			break
	if je:
		print(0)
	elif a[0] == 1 or a[n - 1] == n:
		print(1)
	elif a[0] == n and a[n - 1] == 1:
		print(3)
	else:
		print(2)


for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	if arr == sorted(arr):
		print(0)
	elif arr[0] == 1 or arr[-1] == N:
		print(1)
	elif arr[0] == N and arr[-1] == 1:
		print(3)
	else:
		print(2)


t = int(input())
for zz in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	if l == l1:
		print(0)
	elif l[0] == 1 or l[n - 1] == n:
		print(1)
	elif l[0] == n and l[n - 1] == 1:
		print(3)
	else:
		print(2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sa = sorted(a)
	if a == sa:
		print(0)
	elif a[0] == 1:
		print(1)
	elif a[-1] == n:
		print(1)
	elif a[0] == n and a[-1] == 1:
		print(3)
	else:
		print(2)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mi = min(a)
	mx = max(a)
	b = list(sorted(a))
	if a == b:
		print(0)
	elif a[-1] == b[-1] or a[0] == b[0]:
		print(1)
	elif mi != a[-1] or mx != a[0]:
		print(2)
	else:
		print(3)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	maxx = n
	minn = 1
	if l == sorted(l):
		print(0)
		continue
	elif l[0] == 1 or l[n - 1] == n:
		print(1)
		continue
	elif l[n - 1] == 1 and l[0] == n:
		print(3)
		continue
	else:
		print(2)


from sys import stdin
for test in range(int(input())):
	k = int(input())
	lst = [i for i in range(1, k + 1)]
	arr = list(map(int, input().split()))
	ans = 0
	if arr == lst:
		print(0)
	elif arr[0] == 1 or arr[-1] == k:
		print(1)
	elif arr[0] == k and arr[-1] == 1:
		print(3)
	else:
		print(2)


def zip_sorted(a, b):
	return (zip(*sorted(zip(a, b)))[0], zip(*sorted(zip(a, b)))[1])

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def ncr(n, r):
	return math.comb(n, r)

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def decimal_to_binary(n):
	return bin(n).replace('0b', '')

def binary_to_decimal(s):
	return int(s, 2)
import sys, os.path
import math
from collections import defaultdict, deque
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input()))

def main():
	(t,) = I()
	for t1 in range(t):
		(n,) = I()
		a = I()
		if a == sorted(a):
			print(0)
		elif a[0] == max(a) and a[-1] == min(a):
			print(3)
		elif a[0] == min(a) or a[-1] == max(a):
			print(1)
		else:
			print(2)
main()


for _ in range(int(input())):
	n = int(input())
	lst = [int(value) for value in input().split()]
	if lst == [i for i in range(1, n + 1)]:
		print('0')
	elif lst[0] == 1 or lst[n - 1] == n:
		print('1')
	elif lst[0] == n and lst[n - 1] == 1:
		print('3')
	else:
		print('2')


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sorted(a) == a:
		print(0)
		continue
	if a[0] == n and a[-1] == 1:
		print(3)
		continue
	if a[0] == 1 or a[-1] == n:
		print(1)
		continue
	print(2)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def check_permutation(L):
	n = len(L)
	if L == list(range(1, n + 1)):
		return True
	else:
		return False

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	if check_permutation(A):
		print(0)
		return
	if A[0] == 1 or A[-1] == n:
		print(1)
	elif A[0] == n and A[-1] == 1:
		print(3)
	else:
		print(2)
t = int(input())
for _ in range(t):
	solve()


t_case = int(input())
for i in range(t_case):
	n = int(input())
	arr = [int(i) for i in input().split()]
	s_arr = arr[:]
	s_arr.sort()
	if arr == s_arr:
		print(0)
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	else:
		print(2)


def isSorted(ll):
	for i in range(1, n):
		if ll[i] < ll[i - 1]:
			return False
	return True
out = []
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split(' ')))
	if isSorted(data):
		out.append('0')
	elif data[0] == 1 or data[n - 1] == n:
		out.append('1')
	elif data[0] == n and data[n - 1] == 1:
		out.append('3')
	else:
		out.append('2')
print('\n'.join(out))


import sys
import math
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor, log
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)
N = 20005
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().rstrip().split()))
	A = a.copy()
	A.sort()
	if A == a:
		print(0)
	elif A[0] == a[0] or A[-1] == a[-1]:
		print(1)
	elif A[0] == a[-1] and A[-1] == a[0]:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	a = int(input())
	b = [int(x) for x in input().split()]
	if b == sorted(b):
		print(0)
	elif b[0] == 1 or b[a - 1] == a:
		print(1)
	elif b[0] == a and b[-1] == 1:
		print(3)
	else:
		print(2)


import sys

def main(N, A):
	B = sorted(A)
	C = [a == b for (a, b) in zip(A, B)]
	d = 0
	for i in range(1, N):
		if C[i] != C[i - 1]:
			d += 1
	if d == 0:
		if C[0]:
			return 0
	if C[0] or C[-1]:
		return 1
	if A[0] == N and A[-1] == 1:
		return 3
	return 2
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	N = int(input())
	(*A,) = map(int, input().split())
	ans = main(N, A)
	print(ans)


for i in range(int(input())):
	a = int(input())
	b = [int(x) for x in input().split()]
	c = b[:]
	c.sort()
	if b == c:
		print(0)
	elif c[-1] == b[-1] or c[0] == b[0]:
		print(1)
	elif c[-1] == b[0] and c[0] == b[-1]:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))

	def check():
		for i in range(n):
			if a[i] != i + 1:
				return False
		return True
	if check():
		print(0)
	elif a[0] == 1 or a[n - 1] == n:
		print(1)
	elif a[0] == n and a[n - 1] == 1:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	f = arr[0]
	l = arr[-1]
	for i in range(n):
		if i + 1 != arr[i]:
			break
	else:
		print(0)
		continue
	if f == n and l == 1:
		print(3)
	elif f != 1 and l != n:
		print(2)
	else:
		print(1)


t = int(input())
from sys import stdin, stdout
for _ in range(t):
	n = int(input())
	map1 = map(int, stdin.readline().rstrip().split())
	arr = list(map1)
	if arr == sorted(arr):
		print(0)
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	li = arr.copy()
	li.sort()
	if arr == li:
		print(0)
		continue
	if arr[0] == 1 or arr[-1] == n:
		print(1)
		continue
	elif arr[-1] == 1 and arr[0] == n:
		print(3)
		continue
	else:
		print(2)
		continue


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


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l == sorted(l):
		print('0')
	elif l[0] == 1 or l[len(l) - 1] == len(l):
		print('1')
	elif l[0] == len(l) and l[len(l) - 1] == 1:
		print('3')
	else:
		print('2')


def func(a, n):
	a = tuple(map(int, a.split()[:n]))
	m = max(a)
	mn = min(a)

	def check(lst):
		for i in range(len(lst) - 1):
			if lst[i] > lst[i + 1]:
				return False
		return True
	c1 = check(a[:-1])
	c2 = check(a[1:])
	c3 = a[0] == mn
	if a[-1] == m:
		if c1:
			res = 0
		else:
			res = 1
	elif a[0] == m:
		if c2:
			res = 2
		else:
			res = 2 + int(a[-1] == mn)
	elif a[0] > a[-1]:
		res = 2
	else:
		res = 2 - c3
	return res
for _ in range(int(input())):
	n = int(input())
	a = input()
	print(func(a, n))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr == sorted(arr):
		print(0)
	elif arr[0] == min(arr):
		print(1)
	elif arr[-1] == max(arr):
		print(1)
	elif arr[0] == max(arr) and arr[-1] == min(arr):
		print(3)
	else:
		print(2)


for enumeration in range(int(input())):
	n = int(input())
	array = [int(x) for x in input().split()]
	if array == list(sorted(array)):
		print(0)
	elif array[0] == min(array) or array[-1] == max(array):
		print(1)
	elif array[0] == max(array) and array[-1] == min(array):
		print(3)
	else:
		print(2)


from math import gcd
T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	fcheck = sorted(arr)
	a1 = fcheck[0]
	a2 = fcheck[-1]
	if arr[0] == a1 and arr[-1] == a2:
		t = 0
		for i in range(1, n - 1):
			if arr[i] != fcheck[i]:
				print(1)
				t = 1
				break
		if t != 1:
			print(0)
	elif arr[0] == a1 and arr[-1] != a2:
		print(1)
	elif arr[0] != a1 and arr[-1] == a2:
		print(1)
	elif arr[0] == a2 and arr[-1] == a1:
		print(3)
	else:
		print(2)


from sys import stdin
input = stdin.readline
for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if a[0] == n and a[-1] == 1:
		print(3)
	elif a == sorted(a):
		print(0)
	elif a[0] == 1 or a[-1] == n:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	k = int(input())
	l = list(map(int, input().split()))
	(x, y) = (l.index(min(l)), l.index(max(l)))
	if l == sorted(l):
		print(0)
	elif y == 0 and x == k - 1:
		print(3)
	elif y == k - 1 or x == 0:
		print(1)
	else:
		print(2)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().rstrip().split(' ')))
	c = 0
	for i in range(n):
		if a[i] != i + 1:
			if a[0] == 1 or a[-1] == n:
				c = 1
			elif a[0] == n and a[-1] == 1:
				c = 3
			else:
				c = 2
			break
	print(c)


def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		if a == sorted(a):
			print(0)
		elif a[0] == n and a[-1] == 1:
			print(3)
		elif a[0] == 1 or a[-1] == n:
			print(1)
		else:
			print(2)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


n = int(input())
for _ in range(n):
	x = int(input())
	ls = [int(m) for m in input().split()]
	flag = 1
	for i in range(1, x):
		if ls[i] < ls[i - 1]:
			flag = 0
			break
	if flag == 1:
		print(0)
		continue
	if ls[-1] == 1 and ls[0] == x:
		print(3)
		continue
	if ls[-1] == x or ls[0] == 1:
		print(1)
		continue
	print(2)


T = int(input())
for _ in range(T):
	n = int(input())
	line = input()
	arr = [int(__) for __ in line.split(' ')]
	(min_num, max_num, last) = (arr[0], arr[0], arr[0])
	flag = True
	for x in arr:
		if x < last:
			flag = False
		last = x
		min_num = min(min_num, x)
		max_num = max(max_num, x)
	if flag:
		print(0)
	elif min_num == arr[0] or max_num == arr[-1]:
		print(1)
	elif min_num == arr[-1] and max_num == arr[0]:
		print(3)
	else:
		print(2)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	x = [i for i in arr]
	x.sort()
	if x == arr:
		print(0)
	elif arr[0] == 1 or arr[n - 1] == n:
		print(1)
	elif arr[0] == n and arr[n - 1] == 1:
		print(3)
	else:
		print(2)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = input()
	l = list(map(int, arr.split(' ')))
	c = 0
	if l.index(min(l)) != 0:
		c += 1
	if l.index(max(l)) != n - 1:
		c += 1
	if l.index(max(l)) == 0 and l.index(min(l)) == n - 1:
		c = 3
	if l.index(max(l)) == n - 1 and l.index(min(l)) == 0:
		if l == sorted(l):
			c = 0
		else:
			c = 1
	print(c)


import io
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify
from math import gcd, inf

def solve(N, A):
	sA = sorted(A)
	if sA == A:
		return 0
	if sA[0] == A[0] or sA[-1] == A[-1]:
		return 1
	if sA[-1] == A[0] and sA[0] == A[-1]:
		return 3
	return 2
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solve(N, A)
	print(ans)


testcases = int(input())
while testcases:
	n = int(input())
	inpArr = list()
	inpArr = list(map(int, input().split()))
	t = sorted(inpArr)
	if inpArr == t:
		print('0')
		testcases -= 1
		continue
	c = 0
	if inpArr[0] == 1 or inpArr[n - 1] == n:
		c = 1
	elif inpArr[0] != n or inpArr[n - 1] != 1:
		c = 2
	else:
		c = 3
	print(c)
	testcases -= 1


import sys
t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split(' ')]
	already_sorted = True
	for i in range(1, n):
		if A[i] < A[i - 1]:
			already_sorted = False
			break
	if already_sorted:
		print(0)
	elif A[0] == 1 or A[-1] == n:
		print(1)
	elif A[0] == n and A[-1] == 1:
		print(3)
	else:
		print(2)


def permuate_sort(arr, n):
	if arr[0] == len(arr) and arr[-1] == 1:
		return 3
	for (i, num) in enumerate(arr):
		if num != i + 1:
			break
	else:
		return 0
	if arr[0] == 1 or arr[-1] == n:
		return 1
	return 2
T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(num) for num in input().split()]
	print(permuate_sort(arr, n))


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	if lst == sorted(lst):
		print(0)
	elif lst[n - 1] == n:
		print(1)
	elif lst[n - 1] == 1 and lst[0] == n:
		print(3)
	elif lst[0] == 1:
		print(1)
	else:
		print(2)


colls = int(input())
for _ in range(colls):
	els = int(input())
	elems = list(map(int, input().split()))
	s_elems = sorted(elems)
	if elems == s_elems:
		print(0)
	elif elems[-1] == max(elems) or elems[0] == min(elems):
		print(1)
	elif elems[-1] == min(elems) and elems[0] == max(elems):
		print(3)
	else:
		print(2)


import os
import sys
from io import BytesIO, IOBase

def main():
	import bisect
	import math
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def solve(n, arr):
		if arr == sorted(arr):
			return 0
		elif min(arr) == arr[0] or max(arr) == arr[-1]:
			return 1
		elif min(arr) == arr[-1] and max(arr) == arr[0]:
			return 3
		else:
			return 2
	t = int(input())
	ans = []
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ans.append(solve(n, arr))
	for j in range(len(ans)):
		print(ans[j])
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for i in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	f = 0
	for j in range(0, n):
		if l[j] != j + 1:
			f = 1
			break
	if f == 0:
		print(0)
	elif l[0] == n and l[n - 1] == 1:
		print(3)
	elif l[0] == 1 or l[n - 1] == n:
		print(1)
	else:
		print(2)


t = int(input())
while t:
	t -= 1
	n = int(input())
	num = list(map(int, input().split()))
	is_sorted = True
	for i in range(n - 1):
		if num[i] > num[i + 1]:
			is_sorted = False
			break
	if is_sorted == True:
		print(0)
	elif num[0] == 1 or num[n - 1] == n:
		print(1)
	elif num[0] == n and num[n - 1] == 1:
		print(3)
	else:
		print(2)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	lo = a.index(min(a))
	hi = a.index(max(a))
	if lo == n - 1 and hi == 0:
		print(3)
	elif lo != 0 and hi != n - 1:
		print(2)
	elif lo == 0 and hi != n - 1:
		print(1)
	elif lo != 0 and hi == n - 1:
		print(1)
	else:
		b = list(set(a))
		if a == b:
			print(0)
		else:
			print(1)


t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = sorted(arr)
	if temp == arr:
		print(0)
	elif arr[0] == 1 or arr[-1] == temp[-1]:
		print(1)
	elif arr[-1] == 1 and n > 2:
		if arr[0] == n:
			print(3)
		else:
			print(2)
	else:
		print(2)


def main():
	for i in range(int(input())):
		n = int(input())
		array = list(map(int, input().split()))
		answer = 2
		if array == sorted(array):
			answer = 0
		else:
			if array[0] == 1 or array[n - 1] == n:
				answer = 1
			if array[0] == n and array[n - 1] == 1:
				answer = 3
		print(answer)
main()


for _ in ' ' * int(input()):
	n = int(input())
	a = [*map(int, input().split())]
	if a == sorted(a):
		print(0)
	elif a[0] == 1 or a[-1] == n:
		print(1)
	elif a[0] == n and a[-1] == 1:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l == sorted(l):
		print('0')
		continue
	if l[0] == 1 or l[n - 1] == n:
		print('1')
		continue
	if l[0] == n:
		if l[n - 1] == 1:
			print('3')
		else:
			print('2')
		continue
	else:
		print('2')


import sys, math
from collections import deque, defaultdict
import operator as op
from functools import reduce
from itertools import permutations
import heapq
I = sys.stdin.readline
alpha = 'abcdefghijklmnopqrstuvwxyz'
mod = 10 ** 9 + 7

def ii():
	return int(I().strip())

def li():
	return list(map(int, I().strip().split()))

def mi():
	return map(int, I().strip().split())

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def isPrime(n):
	if n <= 1:
		return False
	elif n <= 2:
		return True
	else:
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

def main():
	ans = ''
	for _ in range(ii()):
		n = ii()
		arr = li()
		if arr == sorted(arr):
			ans += '0\n'
		elif arr[0] != 1:
			if arr[n - 1] == n:
				ans += '1\n'
			elif arr[0] == n and arr[n - 1] == 1:
				ans += '3\n'
			else:
				ans += '2\n'
		else:
			ans += '1\n'
	print(ans)
main()


import sys
sys.setrecursionlimit(10 ** 6)

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

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

def LC():
	return list(input())

def IC():
	return [int(c) for c in input()]

def MI():
	return map(int, sys.stdin.readline().split())
INF = float('inf')
MOD = 10 ** 9 + 7

def solve():
	T = II()
	for t in range(T):
		N = II()
		A = LI()
		Asort = sorted(A)
		if Asort == A:
			print(0)
		elif A[0] == 1 or A[-1] == N:
			print(1)
		elif A[0] == N and A[-1] == 1:
			print(3)
		else:
			print(2)
	return
solve()


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	q = 0
	for (x, y) in enumerate(l):
		if x != n - 1:
			if y < l[x + 1]:
				continue
			else:
				q = 1
				break
	if q == 0:
		print(0)
	elif l[0] == min(l) or l[n - 1] == max(l):
		print(1)
	elif l[0] == max(l) and l[n - 1] == min(l):
		print(3)
	else:
		print(2)


import sys
input = sys.stdin.readline

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


k = int(input())
a = []
import math

def nhap():
	r = input()
	r = r.split()
	r = [int(i) for i in r]
	return r

def kq(a):
	minn = min(a)
	maxx = max(a)
	b = sorted(a)
	if b == a:
		return 0
	if a[0] == maxx and a[-1] == minn:
		return 3
	if a[0] == minn or a[-1] == maxx:
		return 1
	return 2
for i in range(k):
	num = int(input())
	a.append(nhap())
for i in a:
	print(kq(i))


n = int(input())
for i in range(n):
	ni = input()
	a = list(map(int, input().split()))
	if a == sorted(a):
		print(0)
	elif max(a) == a[-1] or min(a) == a[0]:
		print(1)
	elif max(a) == a[0] and min(a) == a[-1]:
		print(3)
	elif len(a) > 2:
		print(2)
	else:
		print(1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	ans = 0
	if arr[0] == len(arr):
		count += 1
	if arr[-1] == 1:
		count += 1
	if count == 2:
		print(3)
	elif count == 1:
		print(2)
	elif count == 0:
		sorted_arr = sorted(arr)
		if arr == sorted_arr:
			print(0)
		elif arr[0] == 1 or arr[-1] == len(arr):
			print(1)
		else:
			print(2)


t = int(input())
l = []
while t > 0:
	n = int(input())
	i = 0
	a = list(map(int, input().split()))
	if a.index(max(a)) == len(a) - 1 or a.index(min(a)) == 0:
		for i in range(len(a) - 1):
			flag = 0
			if a[i] <= a[i + 1]:
				flag = 1
			else:
				break
		if flag == 1:
			print(0)
		else:
			print(1)
	elif a.index(min(a)) == len(a) - 1 and a.index(max(a)) == 0:
		print(3)
	else:
		print(2)
	t = t - 1


from sys import stdin, stdout
import math

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()
	max1 = l1.index(n)
	if l1 == list(sorted(l1)):
		print(0)
	elif l1[0] == 1 or l1[n - 1] == n:
		print(1)
	elif l1[0] == n and l1[n - 1] == 1:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	o = l.copy()
	o.sort()
	if o == l:
		print(0)
		continue
	if l[-1] == 1 and l[0] == n:
		print(3)
		continue
	if l[0] == 1 or l[-1] == n:
		print(1)
		continue
	print(2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	is_sorted = all((arr[i] <= arr[i + 1] for i in range(len(arr) - 1)))
	if is_sorted:
		print(0)
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	else:
		print(2)


def insort(l):
	for i in range(len(l) - 1):
		if l[i] > l[i + 1]:
			return False
	return True

def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		n = int(input())
		lt = list(map(int, input().split()))
		if insort(lt):
			print(0)
		elif lt[0] == 1 or lt[-1] == n:
			print(1)
		elif lt[0] == n and lt[-1] == 1:
			print(3)
		else:
			print(2)
main()


t = int(input())
for _ in range(t):
	i = int(input())
	l = list(map(int, input().split()))
	t = sorted(l)
	if t == l:
		print(0)
	elif l[0] == t[0] or l[-1] == t[-1]:
		print(1)
	elif l[0] == t[-1] and l[-1] == t[0]:
		print(3)
	else:
		print(2)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = sorted(a)
	h = [0] * (n + 1)
	for i in range(n):
		if a[i] == i + 1:
			h[i] = 1
	if b == a:
		print(0)
	elif h[0] == 0 and h[n - 1] == 0 and (a[0] == n) and (a[n - 1] == 1):
		print(3)
	elif h[0] == 0 and h[n - 1] == 0:
		print(2)
	elif h[0] == 0 and h[n - 1] == 1:
		print(1)
	elif h[0] == 1 and h[n - 1] == 0:
		print(1)
	elif h[0] == 1 and h[n - 1] == 1:
		print(1)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	mn = a.index(min(a))
	mx = a.index(max(a))
	b = sorted(a)
	if a == b:
		print('0')
	elif mn == n - 1 and mx == 0:
		print('3')
	elif mn == 0 or mx == n - 1:
		print('1')
	else:
		print('2')
t = int(input())
while t:
	solve()
	t -= 1


def solve():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		c = 0
		if l == sorted(l):
			print(0)
		elif l[0] == 1 or l[n - 1] == n:
			print(1)
		elif l[0] == n and l[n - 1] == 1:
			print(3)
		else:
			print(2)
solve()


def permsort(n):
	l = list(map(int, input().split()))
	x = l.copy()
	x.sort()
	if x == l:
		print(0)
	elif l[0] == x[0] or l[len(l) - 1] == x[len(l) - 1]:
		print(1)
	elif l[0] == x[len(l) - 1] and l[len(l) - 1] == x[0]:
		print(3)
	else:
		print(2)
for _ in range(int(input())):
	permsort(int(input()))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sort_a = sorted(a)
	if a == sort_a:
		print(0)
	else:
		min_a = sort_a[0]
		max_a = sort_a[-1]
		if a[0] == min_a or a[-1] == max_a:
			print(1)
		elif a[0] == max_a and a[-1] == min_a:
			print(3)
		else:
			print(2)


t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	a = list(map(int, input().split()))
	k = []
	k.extend(a)
	a.sort()
	if k[0] != min(a):
		ans += 1
	if k[-1] != max(a):
		ans += 1
	if a[::-1] == k:
		ans += 1
	if k[0] == max(a) and k[-1] == min(a):
		ans = 3
	if k == a:
		print(ans)
	else:
		print(max(1, ans))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr_sort = sorted(arr)
	if arr == arr_sort:
		print(0)
	elif arr[0] == 1 or arr[n - 1] == n:
		print(1)
	elif arr[0] == n and arr[n - 1] == 1:
		print(3)
	else:
		print(2)


t = int(input())
while t > 0:
	n = int(input())
	a = []
	a = input().split()
	a = [int(x) for x in a]
	ans = 2
	if sorted(a) == a:
		ans = 0
	elif a[0] == 1 or a[-1] == n:
		ans = 1
	elif a[0] == n and a[-1] == 1:
		ans = 3
	print(ans)
	t -= 1


import sys
import math
import collections
import operator as op
from collections import deque
from math import gcd, inf, sqrt, pi, cos, sin, ceil, log2, floor, log
from bisect import bisect_right, bisect_left, bisect
from itertools import permutations
from functools import reduce
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(factors)

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
MOD = 1000000007
PMOD = 998244353
LOGN = 30
alp = 'abcdefghijklmnopqrstuvwxyz'
N = int(100000.0)
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().rstrip().split()))
	A = a.copy()
	A.sort()
	if A == a:
		print(0)
	elif A[0] == a[0] or A[-1] == a[-1]:
		print(1)
	elif A[0] == a[-1] and A[-1] == a[0]:
		print(3)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	done = True
	for i in range(n):
		if i + 1 != a[i]:
			done = False
			break
	if done:
		print(0)
		continue
	if a[0] == 1 or a[n - 1] == n:
		print(1)
		continue
	if a[0] == n and a[n - 1] == 1:
		print(3)
		continue
	print(2)


import sys
from math import gcd
testcases = int(input())
while testcases > 0:
	n = int(input())
	a = list(map(int, sys.stdin.readline().split()))
	b = sorted(a)
	if a == b:
		print(0)
	elif a[0] == 1 or a[n - 1] == n:
		print(1)
	elif a[0] == n and a[n - 1] == 1:
		print(3)
	else:
		print(2)
	testcases -= 1


from queue import PriorityQueue
from queue import Queue
import math
from collections import defaultdict
import sys
import operator as op
from functools import reduce
ii = lambda : list(map(int, sys.stdin.readline().split()))
ist = lambda : list(sys.stdin.readline().split())
(t,) = ii()
for _ in range(t):
	(n,) = ii()
	arr = ii()
	if arr == sorted(arr):
		print(0)
	elif n == 2 and arr[0] == 2:
		print(1)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	else:
		print(2)


t = int(input().strip())
for l in range(t):
	n = int(input().strip())
	perm = list(map(int, input().split()))
	sorted_arr = [i for i in range(1, n + 1)]
	if perm == sorted_arr:
		print('0')
	elif perm[0] == 1 or perm[-1] == n:
		print('1')
	elif perm[0] == n and perm[-1] == 1:
		print('3')
	else:
		print('2')


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


for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	s = sorted(w)
	if w[0] == s[-1] and w[-1] == s[0]:
		print(3)
	elif w[0] == s[0] and w[-1] == s[-1]:
		c = 0
		for i in range(n):
			if w[i] == s[i]:
				c += 1
		if c == n:
			print(0)
		else:
			print(1)
	elif w[0] == s[0] and w[-1] != s[-1] or (w[0] != s[0] and w[-1] == s[-1]):
		print(1)
	else:
		print(2)


import math
nomber_test = int(input())
for i in range(nomber_test):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = sorted(a)
	if a1 == a:
		print(0)
	elif a[0] == 1 or a[-1] == n:
		print(1)
	elif a[-1] == 1:
		if a[0] == n:
			print(3)
		else:
			print(2)
	else:
		print(2)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr == list(range(1, n + 1)):
		print(0)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if a == sorted(a):
		print(0)
	elif a[0] == n and a[-1] == 1:
		print(3)
	elif a[0] == 1 or a[-1] == n:
		print(1)
	else:
		print(2)


t = int(input())
for w in range(t):
	n = int(input())
	arr = []
	inp = input().split()
	for i in inp:
		arr.append(int(i))
	arr1 = arr[:]
	arr1.sort()
	if arr1 == arr:
		print(0)
	elif arr[0] == 1 or arr[-1] == n:
		print(1)
	elif arr[-1] == 1 and arr[0] == n:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	l1 = [int(_) for _ in input().split()]
	shit = sorted(l1)
	if l1 == shit:
		print(0)
	elif l1[0] == shit[0] or l1[-1] == shit[-1]:
		print(1)
	elif l1[0] == shit[-1] and l1[-1] == shit[0]:
		print(3)
	else:
		print(2)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	array = []
	array = s.split()
	flag = True
	for i in range(1, n):
		if int(array[i]) < int(array[i - 1]):
			flag = False
			break
	if flag:
		print(0)
	elif array[0] == str(1) or array[n - 1] == str(n):
		print(1)
	elif array[0] == str(n) and array[n - 1] == str(1):
		print(3)
	else:
		print(2)


def main(a):
	n = len(a)
	if a == list(range(1, n + 1)):
		return 0
	if a[0] == 1 or a[-1] == n:
		return 1
	if a[0] == n and a[-1] == 1:
		return 3
	return 2
t = int(input())
inputs = []
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	inputs.append(arr)
for i in inputs:
	print(main(i))


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = get_array()
	if a[0] == n and a[n - 1] == 1:
		print(3)
	elif a[0] != 1 and a[n - 1] != n:
		print(2)
		continue
	elif a[0] != 1:
		print(1)
		continue
	elif a[n - 1] != n:
		print(1)
		continue
	else:
		flag = 0
		if a[0] == 1 and a[n - 1] == n:
			for i in range(1, n - 1):
				if a[i] != i + 1:
					flag = 1
					break
		if flag == 0:
			print(0)
		if flag == 1:
			print(1)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
for _ in range(int(input())):
	n = int(input())
	p = li()
	if all((p[i] < p[i + 1] for i in range(n - 1))):
		print(0)
	elif p[0] == 1 or p[n - 1] == n:
		print(1)
	elif p[0] == n and p[n - 1] == 1:
		print(3)
	else:
		print(2)


t = int(input())
for case in range(1, t + 1):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	s_arr = sorted(arr)
	correct = 0
	for (s, a) in zip(arr, s_arr):
		if s == a:
			correct += 1
		else:
			break
	if correct == n:
		print(0)
	elif arr[0] == s_arr[0] or arr[-1] == s_arr[-1]:
		print(1)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	else:
		print(2)


import sys
from os import path
import math
import time
from math import gcd
MOD = 10 ** 9 + 7
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def test_case():
	t = int(input())
	for _ in range(t):
		k = int(input())
		arr = list(map(int, input().split()))
		MAX_ = 2
		sorted_arr = sorted(arr)
		if sorted_arr == arr:
			print(0)
		elif arr[0] == 1 or arr[-1] == k:
			print(1)
		elif arr[0] == k and arr[-1] == 1:
			print(3)
		else:
			print(2)
test_case()


t = int(input())
for i in range(t):
	k = int(input())
	m = list(map(int, input().split()))
	n = sorted(m)
	if m == n:
		print(0)
	elif n[0] == m[0] or n[-1] == m[-1]:
		print(1)
	elif m[0] == k and m[-1] == 1:
		print(3)
	else:
		print(2)


def main():
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N):
		if A[i] != i + 1:
			break
	else:
		return print(0)
	if A[0] == 1 or A[-1] == N:
		print(1)
	elif A[0] == N and A[-1] == 1:
		print(3)
	else:
		print(2)
T = int(input())
for _ in range(T):
	main()


def fun(ls, n):
	st = sorted(ls)
	if st == ls:
		print(0)
		return
	elif st[0] == ls[0] or st[-1] == ls[-1]:
		print(1)
		return
	elif st[0] == ls[-1] and st[-1] == ls[0]:
		print(3)
		return
	else:
		print(2)
		return
T = int(input())
for i in range(T):
	n = int(input())
	ls = list(map(int, input().split()))
	fun(ls, n)


def mapit():
	temp = list(map(int, input().split()))
	return temp

def solution():
	n = int(input())
	arr = mapit()
	new = arr.copy()
	new.sort()
	if new == arr:
		print(0)
		return
	mn_idx = arr.index(min(arr))
	mx_idx = arr.index(max(arr))
	if mn_idx == 0:
		print(1)
		return
	if mn_idx == n - 1:
		if mx_idx == 0:
			print(3)
			return
		else:
			print(2)
			return
	if mx_idx == n - 1:
		print(1)
	else:
		print(2)
	return
t = int(input())
while t:
	t -= 1
	solution()


import math

def primeFactors(n):
	l = []
	c = 2
	while n > 1:
		if n % c == 0:
			l.append(c)
			n = n / c
		else:
			c = c + 1
	return l

def primeFactors(n):
	l = []
	c = 2
	while n > 1:
		if n % c == 0:
			l.append(c)
			n = n / c
		else:
			c = c + 1
	return l

def prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
	return prime_flag
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l[:]
	l1.sort()
	if l1 == l:
		print(0)
	elif l[0] == 1 and l[n - 1] != n:
		print(1)
	elif l[n - 1] == n and l[0] != 1:
		print(1)
	elif l[0] == 1 and l[n - 1] == n:
		print(1)
	elif l[n - 1] != n and l[0] != 1 and (l[0] != n and l[n - 1] != 0):
		print(2)
	elif l[n - 1] == 1 and l[0] == n:
		print(3)
	elif l[n - 1] == 1 and l[0] != n:
		print(2)
	elif l[0] == n and l[n - 1] != 1:
		print(2)
	else:
		print(3)
	t = t - 1


t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	c = sorted(b)
	if b == c:
		print(0)
	elif b[0] == len(b) and b[-1] == 1:
		print(3)
	elif b[0] != 1 and b[-1] != len(b):
		print(2)
	else:
		print(1)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	c = int(input())
	s = list(map(int, input().split()))
	b = True
	for j in range(c):
		b = b and s[j] == j + 1
	if b:
		print(0)
	elif s[0] == 1 or s[-1] == c:
		print(1)
	elif s[0] == c and s[-1] == 1:
		print(3)
	else:
		print(2)


import sys
input = sys.stdin.readline
import math

def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	ans = [i for i in range(1, n + 1)]
	rev = [i for i in reversed(ans)]
	if lis == ans:
		print(0)
	elif lis[0] == n and lis[-1] == 1:
		print(3)
	elif lis[0] == 1 or lis[-1] == n:
		print(1)
	else:
		print(2)
	return
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = l.copy()
	k.sort()
	if k == l:
		print(0)
	elif l[0] == 1 or l[n - 1] == n:
		print(1)
	elif l[0] == n and l[n - 1] == 1:
		print(3)
	else:
		print(2)


from sys import stdin, stdout

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

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

def num2in():
	(a, b) = map(int, stdin.readline().split())
	return (a, b)

def num3in():
	(a, b, c) = map(int, stdin.readline().split())
	return (a, b, c)

def num4in():
	(a, b, c, d) = map(int, stdin.readline().split())
	return (a, b, c, d)

def num5in():
	(a, b, c, d, e) = map(int, stdin.readline().split())
	return (a, b, c, d, e)

def gcd(a, b):
	while b > 0:
		temp = b
		b = a % b
		a = temp
	return a
t = num1in()
for test in range(t):
	n = num1in()
	arr = arrin()
	tog = 0
	for i in range(n):
		if arr[i] != i + 1:
			tog = 1
			break
	if tog == 0:
		print(0)
	elif arr[0] == 1 and tog == 1:
		print(1)
	elif arr[-1] == n and tog == 1:
		print(1)
	elif arr[0] == n and arr[-1] == 1:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	c = list(b)
	c.sort()
	if b == c:
		print(0)
	elif b[0] == 1 or b[-1] == n:
		print(1)
	elif b[0] == n and b[-1] == 1:
		print(3)
	else:
		print(2)


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
from math import *
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	(n,) = inp()
	a = inp()
	b = sorted(a)
	if b[0] == a[0]:
		if b[1:] == a[1:]:
			print(0)
		else:
			print(1)
	elif b[-1] == a[-1]:
		if b[:-1] == a[:-1]:
			print(0)
		else:
			print(1)
	elif a[0] == b[-1] and a[-1] == b[0]:
		print(3)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	count = 0
	for j in range(n):
		if a[j] != j + 1:
			count = 1
	if a[0] != 1 and a[n - 1] != n:
		count += 1
	if a[0] == n and a[n - 1] == 1:
		count += 1
	print(count)


t = int(input())
for inh in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	sort = True
	moves = 0
	for i in range(1, n):
		if a[i] < a[i - 1]:
			sort = False
			break
	if sort:
		print(0)
	else:
		if a[0] == n and a[n - 1] == 1:
			moves = 3
		elif a[0] == 1 or a[n - 1] == n:
			moves = 1
		else:
			moves = 2
		print(moves)


import sys
from math import gcd
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	a = [*map(int, input().split())]
	f = 0
	for i in range(1, n):
		if a[i] < a[i - 1]:
			f = 1
			break
	if f == 0:
		print(0)
	elif a[0] == 1 or a[n - 1] == n:
		print(1)
	elif a[0] == n and a[n - 1] == 1:
		print(3)
	else:
		print(2)
	t -= 1