Little Q has planted a tree, which initially has only one root node $$$1$$$, which is also a leaf node. Every morning, each leaf node $$$u$$$ will sprout two branches:
After that, node $$$u$$$ is no longer a leaf node, and nodes $$$2u$$$ and $$$2u+1$$$ become new leaf nodes. This tree will grow for $$$n$$$ days, ultimately forming a tree with $$$\left(2^{n+1}-1\right)$$$ nodes, of which $$$2^n$$$ nodes are leaf nodes.
During these $$$n$$$ days, every afternoon, Little Q can choose one of the branches that have already grown to "prune", modifying its length to any positive integer (possibly less than or greater than the original one), or he can choose not to prune any branches at all.
Little Q hopes that after the tree has fully grown, the sum of the lengths of the branches on the simple path from the root node to each leaf node will be pairwise different. You need to find the minimum number of branches that need to be pruned, or indicate that it is impossible to achieve this.
The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 1\,000$$$) indicating the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10$$$), indicating the number of days the tree grows.
The second line contains $$$\left(2^{n+1}-2\right)$$$ integers $$$a_2, a_3, \ldots, a_{2^{n+1}-1}$$$ ($$$1 \le a_i \le 10^8$$$), indicating the length of the branches.
It is guaranteed that the number of test cases with $$$n$$$ greater than $$$7$$$ does not exceed $$$10$$$.
For each test case, output a line containing an integer, indicating the minimum number of branches that need to be pruned if it is possible to meet the requirement, or $$$-1$$$ otherwise.
321 2 4 3 2 121 2 3 3 2 121 2 3 3 1 1
1 2 -1
