Original problem statement (in Polish) can be found here.

The year is 50 B.C. Gaul is entirely occupied by the Romans. Well, not entirely! One small village of indomitable Gauls still holds out against the invaders. And life is not easy for the Roman legionaries who garrison the fortified camps of Totorum, Aquarium, Laudanum and Compendium...

The year is 49 B.C. Gaul is entirely occupied by the Romans. Well, no one could seriously expect one small village to resist the mighty army of the great Roman Empire. Fortunately, thanks to Julius Caesar's infinite generosity (Ave Caesar!), the settlement wasn't razed to the ground. There was no other choice for the villagers than to conform to the new authorities.

But some of the rules of Roman law can be downright ridiculous. As it turns out, even heights of individual stakes in the stockade encircling the village are strictly regulated. Here is an excerpt from the law, laid down by Roman clerks, and approved by the great ruler, Gaius Julius Caesar (Ave Caesar!):

• Every stockade encircling every village in the whole Roman Empire (governed justly by the great Julius Caesar) should have even number of wooden logs.
• Every log in every stockade should have some minimum height, specified in "Weights and Measures Act", article 15, passage 9. Moreover, the logs can be at most 1000 quarters of a sicilicus¹ higher than this minimum height.
• For every log, the adjacent logs have to be both higher or both lower. It symbolizes the harmony in the whole Roman Empire, governed justly by the great Julius Caesar (Ave Caesar!).

¹sicilicus - Roman unit of length, equal to 1/48 of Roman foot.

As one might expect, stockade around the village of indomitable Gauls did not meet the requirements - specifically, it violated the last rule (it did satisfy the first two, though). Now, the villagers have to lower or raise some of the logs, but this is a lot of work. Determine the minimum number of logs that have to be lowered or raised, so that the final stockade will satisfy the rule of harmony.

Input

The first line contains a single integer t, denoting the number of testcases. Then, testcases follow.

Each testcase consist of a single line. It begins with an integer n, indicating the number of logs in the stockade. (2 <= n <= 10⁶, 2 | n), followed by n integers x_i, indicating the difference between the height of the i-th log and the minimal possible height, expressed in quarters of a sicilicus (0 <= x_i <= 1000). i-th log is adjacent to (i+1)-th log, moreover, first log is adjacent to the last log (stockade encircles the village).

Output

For every testcase you should output one integer - minimum number of logs that have to be lowered or raised, so that the stockade satisfies the requirements of Roman law.

Example

Input:

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

Output:

2
0
3

Explanation

In the first case it is enough to lower the third and the fifth log to height 1. In the second case, the stockade already satisfies all the rules. (Ave Caesar!)