#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_EXPR_LEN 1005
#define MAX_TOKEN_LEN 100

char opStack[MAX_EXPR_LEN];
int top = -1;

void push(char c) {
    opStack[++top] = c;
}

char pop() {
    return (top == -1) ? '\0' : opStack[top--];
}

char peek() {
    return (top == -1) ? '\0' : opStack[top];
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

int isValidExpression(const char* expr) {
    int balance = 0;
    for (int i = 0; expr[i]; i++) {
        char c = expr[i];
        if (!(isdigit(c) || isspace(c) || isOperator(c) || c == '(' || c == ')')) {
            return 0; 
        }
        if (c == '(') balance++;
        else if (c == ')') {
            balance--;
            if (balance < 0) return 0;
        }
    }
    return balance == 0;
}

void infixToPostfix(const char* expr) {
    char token[MAX_TOKEN_LEN];
    int i = 0, len = strlen(expr);

    top = -1; 

    while (i < len) {
        if (isspace(expr[i])) {
            i++;
            continue;
        }

        if (isdigit(expr[i])) {
            int j = 0;
            while (i < len && isdigit(expr[i])) {
                token[j++] = expr[i++];
            }
            token[j] = '\0';
            printf("%s ", token);
        }
        /
        else if (expr[i] == '(') {
            push(expr[i]);
            i++;
        }
        
        else if (expr[i] == ')') {
            while (top != -1 && peek() != '(') {
                printf("%c ", pop());
            }
            if (peek() == '(') pop(); 
            i++;
        }
        
        else if (isOperator(expr[i])) {
            char currOp = expr[i];
            while (top != -1 && precedence(peek()) >= precedence(currOp) && peek() != '(') {
                printf("%c ", pop());
            }
            push(currOp);
            i++;
        }
    }

  
    while (top != -1) {
        char op = pop();
        if (op != '(' && op != ')') {
            printf("%c ", op);
        }
    }

    printf("\n");
}


int main() {
    int n;
    scanf("%d\n", &n);

    char expr[MAX_EXPR_LEN];

    for (int i = 0; i < n; i++) {
        fgets(expr, sizeof(expr), stdin);
        expr[strcspn(expr, "\n")] = 0; 

        if (!isValidExpression(expr)) {
            printf("Invalid input\n");
        } else {
            infixToPostfix(expr);
        }
    }

    return 0;
}