Problem Description

A sequence can be decomposed into the sum of unit impulses, but we can still decompose the sequence into the sum of gate function which defined as
  

.
  For simplify we use G (a,b) to represent , Now the question is how to decompose the sequence to maximize the minimum length of gate function. (The length of is b – a + 1). For simplification, you just need to get the minimum length.

Input

The first integer T is the number of test cases
Each case starts with a number N followed by N integers a[i]  
(0<= T <= 10)
(0<= N <= 10000)
(0 <= a[i] <= 2^31)
(We ensure )

Output

The minimum length S

2
6
2 3 4 3 3 1
5
2 2 2 2 2

3
5

Hint

The first case can be decomposed to G(1,5)+G(1,6)+G(2,5)+G(3,3), the minimum length is 1 and it can also be decomposed to G(1,3)+G(1,5)+G(2,6)+G(3,5), the minimum length is 3, so answer is 3.
The second case can be decomposed to 2*G (1, 5).

Author

Jianhe25