More Garden Troubles

Mr. Wincenty owns a garden and is famously the sort of person who cannot stand yard work. Some time after his earlier troubles with fallen leaves, spring arrived and brought a new headache: weeds began sprouting all over the garden. One day, after long hours in his workshop, Mr. Wincenty walked into the garden holding a portable flamethrower.

The garden consists of $N$ plots numbered from $1$ to $N$. Plot $i$ holds a whole number of weeds $c_i$. Firing the flamethrower once at plot $i$ halves the number of weeds in plot $i$ and in the neighboring plots $i-1$ and $i+1$.

Here "halving" means integer division by $2$ (rounding down): $8$ weeds become $4$, and $5$ weeds become $2$. You may also aim the flamethrower at the non-existent plots $0$ or $N+1$; in that case only plot $1$ or only plot $N$ is reduced, respectively.

Determine the minimum number of times Mr. Wincenty must fire the flamethrower so that every plot ends up with $0$ weeds.

The first line contains an integer $Z$ ($1 \le Z \le 10$), the number of test cases. The test cases follow.

Each test case begins with a line containing one integer $N$ ($1 \le N \le 10^6$), the number of plots in the garden. The next line contains $N$ space-separated integers $c_i$ ($0 \le c_i \le 10^6$), the number of weeds in each plot.

For each test case, print on its own line the minimum number of times the flamethrower must be used.