Alfred: "I'll get this to Mr. Fox, but no more. I've sewn you up, I've set your bones, but I won't bury you. I've buried enough members of the Wayne family."

After being promised the software to erase her criminal record, Catwoman agrees to take Batman to Bane. They manage to defeat all of Bane's men but ended up heading into a MAZE trap. Bane would call this maze as the LIS MAZE. He would hide himself in one of the rooms. Each of these rooms have a number (tag) associated with it. The speciality of the maze is that once you enter any room it will only lead you to rooms with a higher tag in the direction you move. Batman and Catwoman decide to move in opposite directions trying their luck to maximize the number of rooms they search. (They can start with any room, need not be the same)

Catwoman: "Never steal from someone you can't outrun, kid."

Input

t, number of testcases.
n, number of rooms.
n integers giving the tag associated with the rooms.

Output

The maximum number of rooms searched.

Constraints

1 ≤ n ≤ 100

Example

Input:
1
6
5 3 4 6 1 2

Output:
5