I found an interesting problem on https://codeforces.com/problemset/problem/1372/C:
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...

I tried it in Python, but could not do it. Can you solve it?
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()