You are given N piles of stones. The piles are numbered 1 to N from left to right. Each pile contains non negative number of stones. Total number of stones in the N piles is 2N-1. In one move you are allowed to move some stones from a pile to an adjacent pile .
You have to tell the minimum number of moves so that after those moves the number of stones are increasing from left to right and the number of stones in each pile is a power of two.
Input
The first line will contain the number of test cases T (1 ≤ T ≤ 1000) and each test case will be of two lines.
First line contains an integer N (1 ≤ N ≤ 60), the number of piles.
The next line contains N space separated integers denoting the number of stones in each pile. The ith integer is the number of stones in the ith pile.
The number of stones in each pile will be in the range [0, 260 - 1].
Output
For each case output a single integer X, the minimum number of moves.
Sample
| Input | Output |
|---|---|
2 5 1 10 7 8 5 3 1 1 5 | 3 1 |
