Binary Tree Lexicographic Number

Call a rooted tree a binary tree if every vertex has $0$, $1$, or $2$ children and, whenever a vertex has a child, that child is designated as either its left child or its right child. A vertex with a single child is therefore a different tree depending on whether that child is the left one or the right one.

The height of a tree is the number of vertices on the longest path from the root to a leaf. The empty tree has height $0$.

A lexicographic order is defined on binary trees. Tree $A$ is lexicographically smaller than tree $B$ when one of the following holds:

• the height of $A$ is smaller than the height of $B$, or
• $A$ and $B$ have the same height and:
  • the left subtree of $A$ is lexicographically smaller than the left subtree of $B$, or
  • the left subtrees of $A$ and $B$ are equal and the right subtree of $A$ is lexicographically smaller than the right subtree of $B$.

If a vertex has no left child, its left subtree is the empty tree; the same applies when it has no right child.

If two trees $A$ and $B$ are different and $A$ is not lexicographically smaller than $B$, then $A$ is lexicographically larger than $B$.

Number every binary tree according to this order. The tree that consists of a single vertex has number $1$. For the given tree, output its number modulo $1\,000\,000\,000$.

The first line contains the number of trees $t$ ($1 \le t \le 1\,000$).

Then $t$ tree descriptions follow. The first line of each description contains the number of vertices $n$ ($1 \le n \le 2\,000$). The vertices are numbered from $1$ to $n$, and vertex $1$ is the root.

The next $n$ lines describe the children. The $i$-th of them contains two integers $l_i$ and $r_i$, the indices of the left and right child of vertex $i$. If vertex $i$ has no left child then $l_i = -1$, and if it has no right child then $r_i = -1$.

Print exactly $t$ lines. The $i$-th line contains the number of the $i$-th tree in the order defined above, taken modulo $1\,000\,000\,000$.