Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Omkar and Baseball

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPatrick 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]$$$

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 01:15:06 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|