Left child, right sibling (2) P58904

Write a program that reads binary trees of natural numbers, and for each one prints the postorder traversal of its general associated tree.

Input

Input starts with m, the number of trees that must be treated. The description of the m trees follow as is explained at the exercise : “”, with one exceptions: The number of nodes is not given, because you do not need to store the trees in any vector to solve this exercise. You can suppose that none of the given trees is empty, but that their right subtrees are empty.

Output

For each binary tree given, your program must print a line with the postorder traversal of the corresponding generated tree. Each element must be preceded by a space.