Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Rise up

By Nafis_Shhriar · Limits 1s, 512 MB

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

InputOutput
2
5
1 10 7 8 5
3
1 1 5
3
1

    Discussion

    Statistics


    78% Solution Ratio

    Tamim_VEarliest, 1M ago

    Tamim_VFastest, 0.0s

    SHOVON26Lightest, 0 B

    mdvirusShortest, 176B

    Submit

    Login to submit