Complete Binary Tree Check

The problem asks you to determine whether a given binary tree is complete. A binary tree is considered complete if every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. The binary tree is given in level-order format where a value of -1 represents a null node.

You are provided with T test cases. For each test case, you are given an integer n and a sequence of n integers representing the level-order traversal of the binary tree. Your task is to output 1 if the binary tree is complete and 0 otherwise.

Note: The input is read from standard input (stdin) and the output must be written to standard output (stdout). All formulas in this description are formatted in LaTeX if needed.

inputFormat

The input begins with an integer T representing the number of test cases. For each test case:

1. The first line contains an integer n, the number of nodes in the binary tree.
2. The second line contains n space-separated integers representing the level-order traversal of the binary tree. A value of -1 denotes a null node.

For example:

5 6 1 2 3 4 5 -1 6 1 2 3 4 -1 5 3 1 2 3 5 1 2 -1 4 5 7 1 2 3 4 5 6 -1

outputFormat

For each test case, output a single line containing either 1 or 0. Output 1 if the binary tree is complete, otherwise output 0.

For example, the output corresponding to the sample input above is:

1 0 1 0 1## sample

5
6
1 2 3 4 5 -1
6
1 2 3 4 -1 5
3
1 2 3
5
1 2 -1 4 5
7
1 2 3 4 5 6 -1

1
0
1
0
1