Ladder

Sangdeok wants to choose lunch with a ladder game. Huiwon wants to draw horizontal rungs so that the ladder produces a specific result.

The ladder has N vertical lines. Each horizontal rung connects two neighboring vertical lines. When a path goes downward and meets a rung, it moves to the other vertical line connected by that rung. No two rungs are drawn at the same height.

For each destination, you are given which starting point must arrive there. Find the minimum number of horizontal rungs needed to produce the required result.

The input consists of T test cases. The first line contains the integer T.

Each test case has two lines. The first line contains N, the number of vertical lines. The second line contains N integers a_1, a_2, ..., a_N. Here, a_i is the number of the starting point that arrives at destination i.

Each starting point arrives at exactly one destination, and N is a positive integer not greater than 1,000.

For each test case, output the minimum number of horizontal rungs needed to produce the required result.