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.File;import java.io.FileInputStream;import java.io.FileNotFoundException;
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;
import java.security.AccessControlException;import java.util.Arrays;import java.util.List;
public class _p001525B {static public void main(final String[] args) throws IOException
{p001525B._main(args);}
static class p001525B extends Solver{public p001525B(){}@Override public void solve()throws 
IOException{int n=sc.nextInt();sc.nextLine();int[]a=Arrays.stream(sc.nextLine().trim().split("\\s+")).filter($s2
->!$s2.isEmpty()).mapToInt(Integer::parseInt).toArray();int res=0;for(int i=0;i<
n;i++){if(a[i]!=i+1){if(a[0]==1 || a[n-1]==n){res=1;}else if(a[0]==n && a[n-1]==
1){res=3;}else{res=2;}break;}}pw.println(res);}static public void _main(String[]args)
throws IOException{new p001525B().run();}}static class MyScanner{private StringBuilder 
cache=new StringBuilder();int cache_pos=0;private int first_linebreak=-1;private 
int second_linebreak=-1;private StringBuilder sb=new StringBuilder();private InputStream 
is=null;public MyScanner(final InputStream is){this.is=is;}public String charToString(final 
int c){return String.format("'%s'",c=='\n'?"\\n":(c=='\r'?"\\r":String.valueOf((char)c)));
}public int get(){int res=-1;if(cache_pos<cache.length()){res=cache.charAt(cache_pos);
cache_pos++;if(cache_pos==cache.length()){cache.delete(0,cache_pos);cache_pos=0;
}}else{try{res=is.read();}catch(IOException ex){throw new RuntimeException(ex);}
}return res;}private void unget(final int c){if(cache_pos==0){cache.insert(0,(char)c);
}else{cache_pos--;}}public String nextLine(){sb.delete(0,sb.length());int c;boolean 
done=false;boolean end=false;while((c=get())!=-1){if(check_linebreak(c)){done=true;
if(c==first_linebreak){if(!end){end=true;}else{cache.append((char)c);break;}}else 
if(second_linebreak!=-1 && c==second_linebreak){break;}}if(end && c!=first_linebreak 
&& c!=second_linebreak){cache.append((char)c);break;}if(!done){sb.append((char)c);
}}return sb.toString();}private boolean check_linebreak(int c){if(c=='\n'|| c=='\r')
{if(first_linebreak==-1){first_linebreak=c;}else if(c!=first_linebreak && second_linebreak
==-1){second_linebreak=c;}return true;}return false;}public int nextInt(){return 
Integer.parseInt(next());}public long nextLong(){return Long.parseLong(next());}
public boolean hasNext(){boolean res=false;int c;while((c=get())!=-1){if(!check_linebreak(c)
&& c!=' '&& c!='\t'){res=true;unget(c);break;}}return res;}public String next(){
sb.delete(0,sb.length());boolean started=false;int c;while((c=get())!=-1){if(check_linebreak(c)
|| c==' '|| c=='\t'){if(started){unget(c);break;}}else{started=true;sb.append((char)c);
}}return sb.toString();}public int nextChar(){return get();}public boolean eof()
{int c=get();boolean res=false;if(c!=-1){unget(c);}else{res=true;}return res;}public 
double nextDouble(){return Double.parseDouble(next());}}static abstract class Solver
{protected String nameIn=null;protected String nameOut=null;protected boolean singleTest
=false;protected MyScanner sc=null;protected PrintWriter pw=null;private int current_test
=0;private int count_tests=0;protected int currentTest(){return current_test;}protected 
int countTests(){return count_tests;}private void process()throws IOException{if(!singleTest)
{count_tests=sc.nextInt();sc.nextLine();for(current_test=1;current_test<=count_tests;
current_test++){solve();pw.flush();}}else{count_tests=1;current_test=1;solve();}
}abstract protected void solve()throws IOException;public void run()throws IOException
{boolean done=false;try{if(nameIn!=null){if(new File(nameIn).exists()){try(FileInputStream 
fis=new FileInputStream(nameIn);PrintWriter pw0=select_output();){select_output();
done=true;sc=new MyScanner(fis);pw=pw0;process();}}else{throw new RuntimeException("File "
+new File(nameIn).getAbsolutePath()+" does not exist!");}}}catch(IOException | AccessControlException 
ex){}if(!done){try(PrintWriter pw0=select_output();){sc=new MyScanner(System.in);
pw=pw0;process();}}}private PrintWriter select_output()throws FileNotFoundException
{if(nameOut!=null){return new PrintWriter(nameOut);}return new PrintWriter(System.out);
}}static abstract class Tester{static public int getRandomInt(final int min,final 
int max){return(min+(int)Math.floor(Math.random()*(max-min+1)));}static public long 
getRandomLong(final long min,final long max){return(min+(long)Math.floor(Math.random()
*(max-min+1)));}static public double getRandomDouble(final double min,final double 
maxExclusive){return(min+Math.random()*(maxExclusive-min));}abstract protected void 
testOutput(final List<String>output_data);abstract protected void generateInput();
abstract protected String inputDataToString();private boolean break_tester=false;
protected void beforeTesting(){}protected void breakTester(){break_tester=true;}
public boolean broken(){return break_tester;}}}
