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 ≤ t ≤ 2000) — the number of test cases.

The first line of the test case contains a single integer n (3 ≤ n ≤ 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.

Example

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].
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class CodeForces {

    public static void main(String[] args) throws IOException {
        reader input = new reader();
        PrintWriter output = new PrintWriter(System.out);
        //BufferedReader bf = new BufferedReader(new FileReader("input.txt"));
        //PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
        //StringTokenizer stk = new StringTokenizer(bf.readLine());
        //int n=Integer.parseInt(stk.nextToken());
        int t=input.nextInt();
        for(int i=0;i<t;i++){
            int n=input.nextInt();
            int arr[]=input.nextIntArray(n);
            boolean check=true;
            int start=0;
            for(int j=1;j<n;j++){
                if(arr[j]>arr[j-1])
                    ;
                else{
                    check=false;
                    break;
                }
            }
            if(check)
                output.println(0);
            else{
                if(arr[0]==1||arr[n-1]==n)
                    output.println(1);
                else if(arr[0]==n && arr[n-1]==1)
                    output.println(3);
                else
                    output.println(2);
            }
        }
        output.close();
    }

    public static int GCD(int a,int b){
        if(a==0)
            return b;
        else
            return GCD(b%a,a);
    }

    public static boolean isPrime(long num){
        if(num==1)
            return false;
        else if(num==2||num==3)
            return true;
        else if(num%2==0||num%3==0)
            return false;
        else{
            for(long i=5;i*i<=num;i+=6){
                if(num%i==0||num%(i+2)==0)
                    return false;
            }
        }
        return true;
    }

    public static void mergesort(long arr[],int start,int end){//start and end must be indexes
        if(start<end) {
            int mid=(start+end)/2;
            mergesort(arr,start,mid);
            mergesort(arr, mid+1, end);
            merge(arr, start,mid,end);
        }
    }
    public static void merge(long arr[],int start,int mid,int end){
        int lsize=mid-start+1,rsize=end-mid;
        long l[]=new long[lsize],r[]=new long[rsize];
        for(int i=start;i<=mid;i++){
            l[i-start]=arr[i];
        }
        for(int i=mid+1;i<=end;i++){
            r[i-mid-1]=arr[i];
        }
        int i=0,j=0,k=start;
        while(i<lsize&&j<rsize){
            if(l[i]<=r[j]){
                arr[k++]=l[i++];
            }else{
                arr[k++]=r[j++];
            }
        }
        while(i<lsize)
            arr[k++]=l[i++];
        while(j<rsize)
            arr[k++]=r[j++];
    }
}

class Pair{
    int start;
    int end;
    Pair(int start,int end){
        this.start = start;
        this.end = end;
    }
}

class Edge{
    int src,dest,weight;
    Edge(int src,int dest,int weight){
        this.src=src;
        this.dest=dest;
        this.weight=weight;
    }
}

class MSTEdge{
    int vertex;
    int distance;
    MSTEdge(int vertex,int distance){
        this.vertex=vertex;
        this.distance=distance;
    }
}

//Undirected Graph
class UGraph{
    ArrayList<ArrayList<Edge>>graph;
    int vertex;
    UGraph(int vertex){
        this.vertex=vertex;
        graph=new ArrayList<>();
        for(int i=0;i<vertex;i++){
            graph.add(new ArrayList<>());
        }
    }
    void addEdge(int u,int v){
        graph.get(u).add(new Edge(u,v,0));
        graph.get(v).add(new Edge(v,u,0));
    }
    void addEdge(int u,int v,int weight){
        graph.get(u).add(new Edge(u,v,weight));
        graph.get(v).add(new Edge(v,u,weight));
    }
    void BFS(int source){
        boolean visited[]=new boolean[vertex];
        LinkedList<Integer>q=new LinkedList<>();
        q.add(source);
        visited[source]=true;
        while(!q.isEmpty()){
            int x=q.removeFirst();
            System.out.print(x+" ");
            for(Edge i:graph.get(x)){
                if(!visited[i.dest]){
                    q.add(i.dest);
                    visited[i.dest]=true;
                }
            }
        }
        System.out.println();
    }
    void BFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                BFS(i);
            }
        }
    }
    int connectedComponentsBFS(){
        boolean visited[]=new boolean[vertex];
        int count=0;
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                count++;
                BFS(i);
            }
        }
        return count;
    }
    void DFS(int source){
        boolean visited[]=new boolean[vertex];
        DFSHelper(source,visited);
        System.out.println();
    }
    void DFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                DFSHelper(i,visited);
                System.out.println();
            }
        }
    }
    void DFSHelper(int source,boolean visited[]){
        visited[source]=true;
        System.out.print(source+" ");
        for(Edge i:graph.get(source)){
            if(!visited[i.dest]){
                DFSHelper(i.dest,visited);
            }
        }
    }
    boolean detectCycleDFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for (int i=0;i<vertex;i++){
            if(!visited[i]){
                if(detectCycleDFSHelper(i,-1,visited))
                    return true;
            }
        }
        return false;
    }
    boolean detectCycleDFSHelper(int source,int parent,boolean visited[]){
        visited[source]=true;
        for(Edge i:graph.get(source)){
            if(!visited[i.dest]){
                if(detectCycleDFSHelper(i.dest,source,visited))
                    return true;
            }
            if(i.dest!=parent)
                return true;
        }
        return false;
    }
    boolean detectCycleBFS(){//O(V+E)
        boolean visited[]=new boolean[vertex];
        for (int i=0;i<vertex;i++){
            if(!visited[i]){
                if(detectCycleBFSHelper(i,visited))
                    return true;
            }
        }
        return false;
    }
    boolean detectCycleBFSHelper(int source,boolean visited[]){
        int parent[]=new int[vertex];
        Arrays.fill(parent,-1);
        LinkedList<Integer>q=new LinkedList<>();
        q.add(source);
        visited[source]=true;
        while(!q.isEmpty()){
            int x=q.removeFirst();
            for(Edge i:graph.get(x)){
                if(!visited[i.dest]){
                    q.add(x);
                    visited[i.dest]=true;
                    parent[i.dest]=x;
                }
                else{
                    if(parent[x]!=i.dest)
                        return true;
                }
            }
        }
        return false;
    }
    int primsMST(){
        boolean MST[]=new boolean[vertex];
        MSTEdge distarr[]=new MSTEdge[vertex];//MST edge stores least distance of a vertex to the MST
        for(int i=0;i<vertex;i++) {
            distarr[i] = new MSTEdge(i, Integer.MAX_VALUE);
        }
        distarr[0].distance=0;
        // Use TreeSet instead of PriorityQueue as the remove function of the PQ is O(n) in java
        TreeSet<MSTEdge>q=new TreeSet<>((a,b)->a.distance-b.distance);
        for(int i=0;i<vertex;i++) {
            q.add(distarr[i]);
        }
        int ans=0;
        while(!q.isEmpty()){
            MSTEdge x=q.pollFirst();
            ans+=x.distance;
            MST[x.vertex]=true;//Adding in MST
            for(Edge i:graph.get(x.vertex)){
                if(!MST[i.dest]){//Vertex not present in MST
                    if(distarr[i.dest].distance>i.weight){//Updating smallest distance from MST vertices to i.dest
                        q.remove(distarr[i.dest]);
                        distarr[i.dest].distance=i.weight;
                        q.add(distarr[i.dest]);
                    }
                }
            }
        }
        return ans;
    }
}

//Directed non-weighted Graph
class DGraph{
    ArrayList<ArrayList<Edge>>graph;
    int vertex;
    DGraph(int vertex){
        this.vertex=vertex;
        graph=new ArrayList<>();
        for(int i=0;i<vertex;i++){
            graph.add(new ArrayList<>());
        }
    }
    void addEdge(int src,int dest){
        graph.get(src).add(new Edge(src,dest,0));
    }
    void addEdge(int src,int dest,int weight){
        graph.get(src).add(new Edge(src,dest,weight));
    }

    boolean detectCycleDFS(){
        boolean visited[]=new boolean[vertex];
        boolean recst[]=new boolean[vertex];
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                if(detectCycleDFSHelper(i,visited,recst))
                    return true;
            }
        }
        return false;
    }
    boolean detectCycleDFSHelper(int index,boolean visited[],boolean recst[]){
        visited[index]=true;
        recst[index]=true;
        for(Edge i:graph.get(index)){
            if(!visited[i.dest]){
                if(detectCycleDFSHelper(i.dest,visited,recst))
                    return true;
            }else{
                if(recst[i.dest])//Back edge present
                    return true;
            }
        }
        recst[index]=false;
        return false;
    }
    ArrayList<Integer> topologicalSortingBFS(){//Kahn's Algorithm which is valid only for directed acyclic graphs
        ArrayList<Integer>ans=new ArrayList<>();
        int indegree[]=new int[vertex];
        for(int i=0;i<vertex;i++){
            for(Edge j:graph.get(i)){
                indegree[j.dest]++;
            }
        }
        LinkedList<Integer>q=new LinkedList<>();
        for(int i=0;i<vertex;i++){
            if(indegree[i]==0)
                q.add(i);
        }
        while(!q.isEmpty()){
            int i=q.removeFirst();
            ans.add(i);
            for(Edge x:graph.get(i)){
                if(--indegree[x.dest]==0){
                    q.add(x.dest);
                }
            }
        }
        return ans;
    }
    boolean detectCycleTopologicalSort(){
        int count=0;
        int indegree[]=new int[vertex];
        for(int i=0;i<vertex;i++){
            for(Edge j:graph.get(i)){
                indegree[j.dest]++;
            }
        }
        LinkedList<Integer>q=new LinkedList<>();
        for(int i=0;i<vertex;i++){
            if(indegree[i]==0)
                q.add(i);
        }
        while(!q.isEmpty()){
            int i=q.removeFirst();
            count++;
            for(Edge x:graph.get(i)){
                if(--indegree[x.dest]==0){
                    q.add(x.dest);
                }
            }
        }
        return (count!=vertex);
    }
    ArrayList<Integer> topologicalSortingDFS(){
        boolean visited[]=new boolean[vertex];
        ArrayDeque<Integer>recst=new ArrayDeque<>();
        for(int i=0;i<vertex;i++){
            if(!visited[i]){
                topologicalSortingDFSHelper(i,visited,recst);
            }
        }
        ArrayList<Integer>ans=new ArrayList<>();
        while(!recst.isEmpty())
            ans.add(recst.pop());
        return ans;
    }
    void topologicalSortingDFSHelper(int index,boolean visited[],ArrayDeque<Integer>recst){
        visited[index]=true;
        for(Edge i:graph.get(index)){
            if(!visited[i.dest])
                topologicalSortingDFSHelper(i.dest,visited,recst);
        }
        recst.push(index);
    }
}

class reader {
    BufferedReader br;
    StringTokenizer st;
    public reader() {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }
    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
    public int[] nextIntArray(int arraySize) {
        int array[] = new int[arraySize];
        for (int i = 0; i < arraySize; i++) {
            array[i] = nextInt();
        }
        return array;
    }
    public long[] nextLongArray(int arraySize) {
        long array[] = new long[arraySize];
        for (int i = 0; i < arraySize; i++) {
            array[i] = nextLong();
        }
        return array;
    }
}
