Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across $n$ sessions follow the identity permutation (ie. in the first game he scores $1$ point, in the second game he scores $2$ points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up! 

Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on $[1,2,3]$ can yield $[3,1,2]$ but it cannot yield $[3,2,1]$ since the $2$ is in the same position. 

Given a permutation of $n$ integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed $10^{18}$.

An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

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

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

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ ($1 \leq a_{i} \leq n$)  — the initial permutation.

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


-----Output-----

For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.


-----Example-----
Input
2
5
1 2 3 4 5
7
3 2 4 5 1 6 7

Output
0
2



-----Note-----

In the first permutation, it is already sorted so no exchanges are needed.

It can be shown that you need at least $2$ exchanges to sort the second permutation.

$[3, 2, 4, 5, 1, 6, 7]$

Perform special exchange on range ($1, 5$)

$[4, 1, 2, 3, 5, 6, 7]$

Perform special exchange on range ($1, 4$)

$[1, 2, 3, 4, 5, 6, 7]$

Difficulty: interview

Starter code:

Solutions:
from math import *

def r1(t):
    return t(input())

def r2(t):
    return [t(i) for i in input().split()]

for _ in range(r1(int)):
    n = r1(int)
    a = r2(int)
    g = True
    for i in range(n):
        if a[i] != i + 1:
            g = False
            break
    if g:
        print(0)
        continue

    g = True
    c = 0
    p = False
    for i in range(n):
        if a[i] != i + 1:
            if p == False:
                c += 1
                p = True
        else:
            p = False
    print(min(c, 2))


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n = ri()
    A = rl()

    first_wrong = -1
    first_break = -1
    skip = False

    for i, a in enumerate(A):
        if i + 1 == a:
            if first_wrong != -1 and first_break == -1:
                first_break = i
        else:
            if first_wrong == -1:
                first_wrong = i
            elif first_break != -1:
                skip = True

    if first_wrong == -1:
        print(0)
    elif not skip:
        print(1)
    else:
        print(2)






mode = 'T'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


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


T = int(input())


for i in range(T):
  n = int(input())
  #n,m = map(int, input().split())
  #a,b = map(int, input().split())
  a = list(map(int,input().split()))
  #a = list(input())
  if a == sorted(a):
    print(0)
    continue
  
  strt = True
  count = 0
  for i in range(n):
    if strt and i+1 != a[i]:
      strt = False
    if not strt and i+1 == a[i]:
      count+=1
  
  end = True
  for i in range(n-1,-1,-1):
    if end and i+1 == a[i]:
      count-=1
    else:
      break
  
  if count==0:
    print(1)
  else:
    print(2)


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    i = 0
    ans = 0
    while i < n:
        if a[i] == i + 1:
            i += 1
            continue
        j = i
        while j < n and a[j] != j + 1:
            j += 1
        ans += 1
        i = j
    print(min(ans, 2))

t = int(input())
for _ in range(t):
    solve()

tests = int(input())
for test in range(tests):
    n = int(input())
    a = [int(i) for i in input().split()]
    l, r = -1, -1
    ans = 1
    for i in range(n):
        if r == -1:
            if l == -1:
                if a[i] != i + 1:
                    if l == -1:
                        l = i
            else:
                if a[i] == i + 1:
                    if r == -1:
                        r = i - 1
        else:
            if a[i] != i + 1:
                ans = 2
                break
    if l == -1:
        print(0)
    else:
        print(ans)


for _ in range(int(input())):
    n = int(input())
    arr = list([int(x)-1 for x in input().split()])
    l = -1
    r = -1
    for i in range(n):
        if arr[i] != i:
            if l == -1:
                l = i
            r = i+1
    if l == -1:
        print(0)
        continue
    ans = 1
    for i in range(l, r):
        if arr[i] == i:
            ans = 2
    print(ans)


import sys
import random
from fractions import Fraction
from math import *
 
def input():
    return sys.stdin.readline().strip()
 
def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def linput():
    return list(input())
 
def rinput():
    return list(map(int, tinput()))

def fiinput():
    return list(map(float, tinput()))
 
def rlinput():
    return list(map(int, input().split()))
def trinput():
    return tuple(rinput())

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

def NOYES(fl):
    if fl:
        print("NO")
    else:
        print("YES")
def YESNO(fl):
    if fl:
        print("YES")
    else:
        print("NO")
    
def main():  
    n = iinput()
    #k = iinput() 
    #m = iinput() 
    #n = int(sys.stdin.readline().strip()) 
    #n, k = rinput()
    #n, m = rinput()
    #m, k = rinput()
    #n, k, m = rinput()
    #n, m, k = rinput()
    #k, n, m = rinput()
    #k, m, n = rinput() 
    #m, k, n = rinput()
    #m, n, k = rinput()
    #q = srlinput()
    #q = linput()
    q = rlinput()
    w = q.copy()
    if q == sorted(w):
        print(0)
    else:
        res = 1
        for i in range(n):
            if i + 1 == q[i]:
                res = 2
        if res == 1:
            print(1)
        else:
            l, r = 0, n - 1
            for i in range(n):
                if i + 1 != q[i]:
                    l = i
                    break
            for i in range(n - 1, l, -1):
                if i + 1 != q[i]:
                    r = i
                    break
            q = q[l:r + 1]
            n = len(q)
            m = min(q)
            for i in range(n):
                if m + i == q[i]:
                    print(2)
                    return 0
            print(1)
            
    
        
    

for i in range(iinput()):
    main()


tt = int(input())

for loop in range(tt):

    n = int(input())
    a = list(map(int,input().split()))

    cnt = 0
    for i in range(n):

        if a[i] != i+1 and cnt % 2 == 0:
            cnt += 1
        elif a[i] == i+1 and cnt % 2 == 1:
            cnt += 1

    if cnt == 0:
        print(0)
    elif cnt <= 2:
        print(1)
    else:
        print(2)


import math

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    prev = True
    num = 0
    for j in range(n):
        if prev and a[j] != j+1:
            num += 1
            prev = False
        elif a[j] == j+1:
            prev = True
    if num > 2:
        print(2)
    else:
        print(num)