Sdjpx Is Happy

Problem Description

Sdjpx is a powful man,he controls a big country.There are n soldiers numbered 1~n(1<=n<=3000).But there is a big problem for him.He wants soldiers sorted in increasing order.He find a way to sort,but there three rules to obey. 1.He can divides soldiers into K disjoint non-empty subarrays. 2.He can sort a subarray many times untill a subarray is sorted in increasing order. 3.He can choose just two subarrays and change thier positions between themselves. Consider A = [1 5 4 3 2] and P = 2. A possible soldiers into K = 4 disjoint subarrays is:A1 = [1],A2 = [5],A3 = [4],A4 = [3 2],After Sorting Each Subarray:A1 = [1],A2 = [5],A3 = [4],A4 = [2 3],After swapping A4 and A2:A1 = [1],A2 = [2 3],A3 = [4],A4 = [5]. But he wants to know for a fixed permutation ,what is the the maximum number of K? Notice: every soldier has a distinct number from 1~n.There are no more than 10 cases in the input.

Input

First line is the number of cases. For every case: Next line is n. Next line is the number for the n soildiers.

Output

the maximum number of K. Every case a line.

Sample Input

2

5

1 5 4 3 2

5

4 5 1 2 3

Sample Output

4

2

Hint

Test1: Same as walk through in the statement. Test2: [4 5] [1 2 3] Swap the 2 blocks: [1 2 3] [4 5].

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6049