Bob lives in a chaotic country with cities in a row, numbered from to . These cities are owned by different lords, and the -th cities currently belongs to the -th lord. To simply problems, we assume there are lords in the country, and they are also numbered from to . Some lords may take control of multiple cities, while some new-born lords have not got any cities yet.

Obviously, the greedy lords are not satisfied with the number of territories they have, so the country is constantly at war. Bob wants to change that, by making all the cities belong to the same lord!

Bob can perform some magical operations to support his grand plan. With the help of each magic, Bob can do the following:

• Choose some cities with consecutive indices such that they belong to the same lord, and assign them to any other lord.

As magics are really tiring, Bob wants to know the minimum number of such operations he needs to use to make all the cities belong to one lord.

The first line contains a single integer  --- the number of test cases.

The first line of each test case contains an integers  --- the number of cities in the country.

The second line of each test case contains n integers  --- the i-th city was originally owned by the -th lord. It is guaranteed that 

It is guaranteed that the sum of n over all test cases doesn't exceed 6000.

For each test case, print a single integer indicating the answer.

2
8
4 3 1 2 1 1 3 3
5
1 2 3 2 1

3
2