/*HDU 6049 - Sdjpx Is Happy [ 枚举,剪枝 ]  |  2017 Multi-University Training Contest 2题意：	长度为N的排列 N <= 3000	排序分三个步骤：		1.原数组分为不相交的K段		2.每段都独立排序		3.选择其中两段swap	问按步骤能成功排序的K能取到的最大是多少分析：	先预处理出任意段的最小值和最大值	再处理出任意[l,r]段最多能分成多少段有效段，用f[i,j]表示	所谓的有效段首先满足 Max[i,j]-Min[i,j] = j-i	再满足其中每段依此递增，即前一段的最大值 == 后一段的最小值-1	设需要交换的前一段为[i, j] 后一段为[k, t]	枚举i,j，则 t = Max[i][j]，再枚举k，更新答案	虽然枚举复杂度大，但可以剪枝	比如要求：f[i,j] > 0 && i 如果不为 1 则 Min[1,i-1] = 1, Max[1, i-1] = i-1	类似的对k, t剪枝*/#include <bits/stdc++.h>using namespace std;const int N = 3005;int Max[N][N], Min[N][N];int f[N][N];int t, n;int a[N], last[N];void init(){    memset(f, 0, sizeof(f));    int i, j, k;    for (i = 1; i <= n; i++) Max[i][i] = Min[i][i] = a[i];    for (k = 2; k <= n; k++)        for (i = 1; i+k-1 <= n; i++)        {            j = i+k-1;            Max[i][j] = max(Max[i+1][j], Max[i][i]);            Min[i][j] = min(Min[i+1][j], Min[i][i]);        }    for (i = 1; i <= n; i++) f[i][i] = 1, last[i] = i;    for (k = 2; k <= n; k++)        for (i = 1; i+k-1 <= n; i++)        {            j = i+k-1;            if (Max[i][j] - Min[i][j] != j-i) continue;            if (Min[i][last[i]] != Min[i][j]) f[i][j] = 1;            else f[i][j] = f[i][last[i]] + 1;            last[i] = j;        }}int ans;void solve(){    ans = f[1][n];    for (int i = 1; i <= n; i++)    {        if ( i != 1 && (!f[1][i-1] || Max[1][i-1] != i-1)) continue;        for (int j = i; j <= n; j++)        {            if (!f[i][j]) continue;            int t = Max[i][j];            if (t != n && (!f[t+1][n] || Min[t+1][n] != t+1 || Max[t+1][n] != n)) continue;            for (int k = t; k > j; k--)            {                if (!f[k][t] || Min[k][t] != i ) continue;                if (k > j+1)                {                   if (!f[j+1][k-1] || Max[k][t] != Min[j+1][k-1]-1 || Min[i][j] != Max[j+1][k-1]+1) continue;                }                else                {                    if (Max[k][t] != Min[i][j]-1) continue;                }                ans = max(ans, f[1][i-1] + 2 + f[j+1][k-1] + f[t+1][n]);            }        }    }}int main(){    scanf("%d", &t);    while (t--)    {        scanf("%d", &n);        for (int i = 1; i <= n; i++) scanf("%d", a+i);        init();        solve();        printf("%d\n", ans);    }}