C. Omkar and Baseball

C. Omkar and Baseball

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 nn sessions follow the identity permutation (ie. in the first game he scores 11 point, in the second game he scores 22 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][1,2,3] can yield [3,1,2][3,1,2] but it cannot yield [3,2,1][3,2,1] since the 22 is in the same position.

Given a permutation of nn 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 10181018.

An array aa is a subarray of an array bb if aa can be obtained from bb 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 tt (1≤t≤1001≤t≤100). Description of the test cases follows.

The first line of each test case contains integer nn (1≤n≤2⋅1051≤n≤2⋅105)  — the length of the given permutation.

The second line of each test case contains nn integers a1,a2,...,ana1,a2,...,an (1≤ai≤n1≤ai≤n)  — the initial permutation.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

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

Example

input

Copy

2
5
1 2 3 4 5
7
3 2 4 5 1 6 7

output

Copy

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 22 exchanges to sort the second permutation.

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

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

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

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

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

=========================================================================

显然递增的肯定是0

如果有一段连续的，其中每个数字都不在原位置，那么把这些数字归到原位置那么就一定不会跟原来的顺序产生任何重叠，也就是耗费1

要是有多段连续的，先将整个变成不同于原来的，也不同于递增的，再将其变成递增的

这里不太好证明为什么一定会存在一个介于两者之间，不同与二者的排列，不妨进行dfs验证一下5

的

# include
# include
# include
 
using namespace std;
 
int a[200000+10];
int main ()
{
   int t;
   cin>>t;
 
   while(t--)
   {
       int n;
       cin>>n;
 
       for(int i=1;i<=n;i++)
       {
           int x;
           cin>>x;
 
           if(x==i)
            a[i]=1;
           else
            a[i]=0;
       }
 
       int cnt=0;
       a[n+1]=1;
       for(int i=1;i<=n;i++)
       {
           if(a[i]==0&&a[i+1])
           {
               cnt++;
 
           }
       }
 
       cout<<min(cnt,2)<
    }
 
    return  0;
 
}