For a given array of integers, reach to the end of the array from the 0th index with minimum number of moves. Moves possible at each index:

Move from index i to index (i+1)

Move from index i to index (i-1)

Move from index i to index j, if a[i] == a[j]

Input

The first line of each test case contains a single integer T denoting the number of test cases. Each test consists of two lines. First line denotes N the number of elements in the array. Second line contains N space separated integers.

Output

For each test case, output a single line containing minimum number of moves possible

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 20

1 ≤ Ai ≤ 105

Example

Input:

2

6

1 2 3 4 5 6

11

2 3 5 1 4 3 2 6 7 8 4

Output:

5

4