Problem Description

Given the pseudo-code of a function $Build-Tree(A,id,L,R)$:

where $A$ is given in input, $id$ is the number of node, $L$ ,$R$ is the left position and the right position of $A$

Require the number of nodes created by $Build-Tree(A,root,1,n)$.

Input

The first line contains an integer $T$ $(1\leq T\leq 5)$ representing the number of test cases.

For each test case, the first contain one integer $n(1 \le n \le 2*10^5)$.

The second line contain n integers $A_i$$(1 \le A_i \le 10^9)$.

Output

For each test output one line, the number of nodes created by $Build-Tree(A,root,1,n)$.

样例1:
1
7
4 3 5 2 6 7 1
样例2:
2
4
2 2 5 3
10
21 10 5 89 12 3 42 13 55 76

样例1:

11

样例2:

6
15