#include <functional>
#include <iostream>
#include <vector>

class BinaryTree {
public:
    using NodeIdx = int;

    struct Node {
        char value;
        NodeIdx left = -1, right = -1;
    };

    enum class FuncEntry { Pre, In, Post };

    NodeIdx root = -1;
    std::vector<Node> nodes;

    void init_with_lines(const std::vector<std::string>& lines) {
        nodes.reserve(lines.size());
        std::vector<int> lines_dashes(lines.size());
        int idx = 0;
        root = init_with_lines(lines, 0, idx);
    }

    std::string prefix_traverse() {
        std::string traverse;
        traverse.reserve(nodes.size());
        dfs([&traverse, this](NodeIdx node, int dfs_depth) {
            traverse += nodes[node].value;
        }, FuncEntry::Pre);
        return traverse;
    }

    std::string infix_traverse() {
        std::string traverse;
        traverse.reserve(nodes.size());
        dfs([&traverse, this](NodeIdx node, int dfs_depth) {
            traverse += nodes[node].value;
        }, FuncEntry::In);
        return traverse;
    }

    std::string postfix_traverse() {
        std::string traverse;
        traverse.reserve(nodes.size());
        dfs([&traverse, this](NodeIdx node, int dfs_depth) {
            traverse += nodes[node].value;
        }, FuncEntry::Post);
        return traverse;
    }

protected:
    NodeIdx init_with_lines(const std::vector<std::string>& lines,
                            int depth, int& idx) {
        if (idx >= lines.size() || lines[idx].size() - 1 < depth) { return -1; }
        char value;
        if ((value = lines[idx][lines[idx].size() - 1]) == '*') {
            idx++;
            return -1;
        }
        const NodeIdx node_idx = nodes.size();
        nodes.push_back(Node{value});
        idx++;
        nodes[node_idx].left = init_with_lines(lines, depth + 1, idx);
        nodes[node_idx].right = init_with_lines(lines, depth + 1, idx);
        return node_idx;
    }

    void dfs(const std::function<void(NodeIdx, int)>& func,
             FuncEntry func_entry = FuncEntry::Pre,
             int dfs_depth = 0,
             NodeIdx node = -1
    ) {
        if (dfs_depth == 0) { node = root; }
        if (func_entry == FuncEntry::Pre) { func(node, dfs_depth); }
        if (nodes[node].left != -1) { dfs(func, func_entry, dfs_depth + 1, nodes[node].left); }
        if (func_entry == FuncEntry::In) { func(node, dfs_depth); }
        if (nodes[node].right != -1) { dfs(func, func_entry, dfs_depth + 1, nodes[node].right); }
        if (func_entry == FuncEntry::Post) { func(node, dfs_depth); }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    while (n--) {
        std::vector<std::string> lines;
        std::string s;
        while (std::cin >> s && s != "0") {
            lines.push_back(s);
        }

        BinaryTree binary_tree;
        binary_tree.init_with_lines(lines);

        std::cout << binary_tree.prefix_traverse() << std::endl
            << binary_tree.postfix_traverse() << std::endl
            << binary_tree.infix_traverse() << std::endl << std::endl;
    }

    return 0;
}