Iris has a tree rooted at vertex (1). Each vertex has a value of (\mathtt 0) or (\mathtt 1). Let's consider a leaf of the tree (the vertex (1) is never considered a leaf) and define its weight . Construct a string formed by the values of the vertices on the path starting at the root and ending in this leaf. Then the weight of the leaf is the difference between the number of occurrences of (\mathtt{10}) and (\mathtt{01}) substrings in it. Take the following tree as an example. Green vertices have a value of (\mathtt 1) while white vertices have a value of (\mathtt 0). Let's calculate the weight of the leaf (5): the formed string is (\mathtt{10110}). The number of occurrences of substring (\mathtt{10}) is (2), the number of occurrences of substring (\mathtt{01}) is (1), so the difference is (2 - 1 = 1). Let's calculate the weight of the leaf (6): the formed string is (\mathtt{101}). The number of occurrences of substring (\mathtt{10}) is (1), the number of occurrences of substring (\mathtt{01}) is (1), so the difference is (1 - 1 = 0). The score of a tree is defined as the number of leaves with non-zero weight in the tree. But the values of some vertices haven't been decided and will be given to you as (?). Filling the blanks would be so boring, so Iris is going to invite Dora to play a game. On each turn, one of the girls chooses any of the remaining vertices with value (?) and changes its value to (\mathtt{0}) or (\mathtt{1}), with Iris going first . The game continues until there are no vertices with value (\mathtt{?}) left in the tree. Iris aims to maximize the score of the tree, while Dora aims to minimize that. Assuming that both girls play optimally, please determine the final score of the tree. Each test consists of multiple test cases. The first line contains a single integer (t) ((1 \leq t \leq 5\cdot 10^4)) — the nu