# Mark the Dust Sweeper solution codeforces

## Mark the Dust Sweeper solution codeforces

Mark is cleaning a row of n rooms. The i-th room has a nonnegative dust level ai. He has a magical cleaning machine that can do the following three-step operation.

• Select two indices <i<j such that the dust levels ai+1ai+11aj−1 are all strictly greater than 00.
• Set ai to 1ai−1.
• Set aj to +1aj+1.

Mark’s goal is to make 1=2==1=0a1=a2=…=an−1=0 so that he can nicely sweep the n-th room. Determine the minimum number of operations needed to reach his goal.

Input

## Mark the Dust Sweeper solution codeforces

The first line contains a single integer t (11041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer n (221052≤n≤2⋅105) — the number of rooms.

The second line of each test case contains n integers 1a12a2, …, an (01090≤ai≤109) — the dust level of each room.

It is guaranteed that the sum of n across all test cases does not exceed 21052⋅105.

Output

## Mark the Dust Sweeper solution codeforces

For each test case, print a line containing a single integer — the minimum number of operations. It can be proven that there is a sequence of operations that meets the goal.

Example

input

Copy
4
3
2 0 0
5
0 2 0 2 0
6
2 0 3 0 4 6
4
0 0 0 10


output

Copy
3
5
11
0

Note

## Mark the Dust Sweeper solution codeforces

In the first case, one possible sequence of operations is as follows.

• Choose =1i=1 and =2j=2, yielding the array [1,1,0][1,1,0].
• Choose =1i=1 and =3j=3, yielding the array [0,1,1][0,1,1].
• Choose =2i=2 and =3j=3, yielding the array [0,0,2][0,0,2].

At this point, 1=2=0a1=a2=0, completing the process.In the second case, one possible sequence of operations is as follows.

• Choose =4i=4 and =5j=5, yielding the array [0,2,0,1,1][0,2,0,1,1].
• Choose =2i=2 and =3j=3, yielding the array [0,1,1,1,1][0,1,1,1,1].
• Choose =2i=2 and =5j=5, yielding the array [0,0,1,1,2][0,0,1,1,2].
• Choose =3i=3 and =5j=5, yielding the array [0,0,0,1,3][0,0,0,1,3].
• Choose =4i=4 and =5j=5, yielding the array [0,0,0,0,4][0,0,0,0,4].

In the last case, the array already satisfies the condition.