AT_arc229_b [ARC229B] Halving Subtraction

You are given a length- $ N $ sequence of non-negative integers $ A=(A_1,A_2,\dots,A_N) $ . You can perform the following operation on $ A $ any number of times, possibly zero: - Choose a positive integer $ x_0 $ , and set $ x=x_0 $ . Then, for $ i=1,2,\ldots,N $ in this order, do the following: - Subtract $ x $ from $ A_i $ , and replace $ x $ with $ \displaystyle \left\lfloor \frac x2\right\rfloor $ . Determine whether it is possible to make all elements of $ A $ equal to $ 0 $ , and if it is possible, find the minimum number of operations required to do so. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the answers for the test cases in order, separated by newlines. For each test case, if it is possible to make all elements of $ A $ equal to $ 0 $ , output the minimum number of operations required to do so; if it is not possible, output `-1`.

### Sample Explanation 1 Consider the first test case. By performing the operations as follows, you can make all elements of $ A $ equal to $ 0 $ in two operations: - Choose $ x_0=3 $ . $ A=(10,4) $ becomes $ A=(7,3) $ . - Choose $ x_0=7 $ . $ A=(7,3) $ becomes $ A=(0,0) $ . It is impossible to make all elements of $ A $ equal to $ 0 $ in fewer than two operations, so output $ 2 $ on the first line. ### Constraints - $ 1\le T\le 10^4 $ - $ 1\le N\le 30 $ - $ 0\le A_i\le 10^9 $ - All input values are integers.