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].
// --------------------------------------------------<TEMPLATE>--------------------------------------------------
// --------------------<optimizations>--------------------
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
*/
// -------------------</optimizations>--------------------

// ---------------<Headers and namespaces>----------------
#include <bits/stdc++.h>
using namespace std;

/*
#include <ext/pb_ds/assoc_container.hx>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/

// ---------------</Headers and namespaces>---------------

// -----------------<Defines and typedefs>----------------
// typedef tree<int,null_type,less<int>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set; // use less_equal for multiset
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the iterator to kth largest element.(0-based)

typedef long double LD;
typedef long long ll;
#define int ll

#define pb push_back
#define mp make_pair

#define rep(i,n) for (int i = 0; i < n; i++)
#define ford(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()

typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define F first
#define S second

#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >

#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())

#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))


// ----------------<Defines and typedefs>----------------
#define PRECISION(x) cout << fixed << setprecision(x);
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// ----------------</Defines and typedefs>----------------

// ------------------------<Consts>-----------------------
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI = acos(-1);

#ifdef int
const int INF = 1e18;
#else
const int INF = 1e9;
#endif

const int MOD =  1e9 + 7;
const int FMOD = 998244353;
const double eps = 1e-9;
// -----------------------</Consts>-----------------------

// -------------------<Debugging stuff>-------------------
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// ------------------</Debugging stuff>-------------------

/*
// -------------------------<RNG>-------------------------
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.

// ------------------------</RNG>-------------------------



// ----------------------<MATH>---------------------------
template<typename T> T gcd(T a, T b) {return (b ? __gcd(a, b) : a);}
template<typename T> T lcm(T a, T b) {return (a * (b / gcd(a, b)));}
int add(int a, int b, int c = MOD) {int res = a + b; return (res >= c ? res - c : res);}
int mod_neg(int a, int b, int c = MOD) {int res; if (abs(a - b) < c)res = a - b; else res = (a - b) % c; return (res < 0 ? res + c : res);}
int mul(int a, int b, int c = MOD) {ll res = (ll)a * b; return (res >= c ? res % c : res);}
int muln(int a, int b, int c = MOD) {ll res = (ll)a * b; return ((res % c) + c) % c;}
ll mulmod(ll a, ll b, ll m = MOD) {ll q = (ll)(((LD)a * (LD)b) / (LD)m); ll r = a * b - q * m; if (r > m)r %= m; if (r < 0)r += m; return r;}
template<typename T>T expo(T e, T n) {T x = 1, p = e; while (n) {if (n & 1)x = x * p; p = p * p; n >>= 1;} return x;}
template<typename T>T power(T e, T n, T m = MOD) {T x = 1, p = e; while (n) {if (n & 1)x = mul(x, p, m); p = mul(p, p, m); n >>= 1;} return x;}
template<typename T>T extended_euclid(T a, T b, T &x, T &y) {
    T xx = 0, yy = 1; y = 0; x = 1; while (b) {
        T q = a / b, t = b; b = a % b; a = t; \
        t = xx; xx = x - q * xx; x = t; t = yy; yy = y - q * yy; y = t;
    } return a;
}
template<typename T>T mod_inverse(T a, T n = MOD) {T x, y, z = 0; T d = extended_euclid(a, n, x, y); return (d > 1 ? -1 : mod_neg(x, z, n));}

const int FACSZ = 1e4; // Make sure to change this

int fact[FACSZ], ifact[FACSZ];

void precom(int c = MOD) {
    fact[0] = 1;
    FOR(i, 1, FACSZ) fact[i] = mul(fact[i - 1], i, c);
    ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
    REPD(i, FACSZ - 1) {
        ifact[i] = mul(i + 1, ifact[i + 1], c);
    }
}

int ncr(int n, int r, int c = MOD) {
    return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
}
*/
// ----------------------</MATH>--------------------------

// ------------------------------<MATRIX>-------------------------------

const long long MOD2 = static_cast<long long>(MOD) * MOD;

struct Matrix
{
	vector< vector<int> > mat;
	int n_rows, n_cols;

	Matrix() {}

	Matrix(vector< vector<int> > values): mat(values), n_rows(values.size()),
		n_cols(values[0].size()) {}

	static Matrix identity_matrix(int n)
	{
		vector< vector<int> > values(n, vector<int>(n, 0));
		for (int i = 0; i < n; i++)
			values[i][i] = 1;
		return values;
	}

	Matrix operator*(const Matrix &other) const
	{
		int n = n_rows, m = other.n_cols;
		vector< vector<int> > result(n_rows, vector<int>(n_cols, 0));
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				long long tmp = 0;
				for (int k = 0; k < n_cols; k++) {
					tmp += mat[i][k] * 1ll * other.mat[k][j];
					while (tmp >= MOD2)
						tmp -= MOD2;
				}
				result[i][j] = tmp % MOD;
			}

		return move(Matrix(move(result)));
	}

	inline bool is_square() const
	{
		return n_rows == n_cols;
	}
};

// binary exponentiation, returns a^p
Matrix pw(Matrix a, int p) {
	Matrix result = Matrix::identity_matrix(a.n_cols);
	while (p > 0) {
		if (p & 1)
			result = a * result;
		a = a * a;
		p >>= 1;
	}
	return result;
}

// ----------------------------</MATRIX>-------------------------------------

//DONT FUCKING CODE TILL YOU HAVE THE COMPLETE IDEA!!!!!
//DONT SUBMIT A FUCKING GUESS !!!

// --------------------------------------------------</TEMPLATE>--------------------------------------------------

void solvethetestcase() {
	int n;
	cin >> n;

	vi v(n);
	int index = 0;
	rep(i, n) {
		cin >> v[i];
		if (v[i] == 1) {
			index = i;
		}
	}

	int ans = 0;



	if (is_sorted(all(v))) {
		cout << 0 << "\n"; return;
	}

	 if (index == 0) {
		cout << 1 << "\n";
		return;
	}

	if (index < n - 1) {
		vi v1;
		rep(i, n - 1) {
			v1.pb(v[i]);
		}

		if (is_sorted(all(v1))) {

		} else {
			ans++;
		}

		sort(all(v1));
		v1.pb(v[n - 1]);

		if (is_sorted(all(v1))) {

		} else {
			ans++;
		}

		cout << ans << "\n";
	} else {
		vi v1, v2, v3;
		ford(i, 1, n) {
			v1.pb(v[i]);
		}
		debug(v1);

		sort(all(v1));
		ans++;

		v2.pb(v[0]);
		rep(i, v1.size() - 1) {
			v2.pb(v1[i]);
		}
		debug(v2);


		sort(all(v2));
		ans++;

		ford(i, 1, v2.size()) {
			v3.pb(v2[i]);
		}
		v3.pb(v1[v1.size() - 1]);
		debug(v3);

		if (is_sorted(all(v3))) {

		} else {ans++;}

		cout << ans << "\n";

	}

}







/*
0. Enough array size? Enough array size? integer overflow?

1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?

2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?

3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/

signed main() {
//comment for kickstart
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	// for getting input frm input1.txt
	freopen("output.txt", "w", stdout);
	// for getting output frm output1.txt
#else
#endif
	PRECISION(12);
	FAST_IO
	int t = 1;

	// (UNCOMMENT FOR MULTIPLE TEST CASES)
	cin >> t;



	ford(testcase, 1, t + 1) {
		//uncomment for kickstart
		//cout << "Case #" << testcase << ": ";
		solvethetestcase();




	}


}




