J. Making 0s
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ with $$$n$$$ elements, $$$n = 4^p, 0 \le p \le 10, -10^9 \le a_i \le 10^9$$$, you can perform the following operation.

1. Choose an integer $$$k, 0 \le k \le p$$$.

2. Divide $$$a$$$ into $$$4^k$$$ consecutive segments of length $$$4^{p - k}$$$.

3. Choose one of these segments and either add $$$1$$$ or subtract $$$1$$$ from all the elements in that segment.

Find the minimum number of operations to make the entire array $$$0$$$.

Input

The first line has a single integer $$$t$$$, the number of tests. ($$$1 \le t \le 4^{9}$$$)

The first line of each test case has a single integer $$$n$$$. ($$$1 \le n \le 4^{10}$$$)

The second line of each test case has $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$. ($$$-10^9 \le a_i \le 10^9$$$)

The sum of $$$n$$$ over all test cases doesn't exceed $$$4^{10}$$$.

Output

For each test case output a single integer, the minimum number of operations.

Example
Input
3
1
3
4
1 4 3 4
16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1
Output
3
7
3