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

#define MAX_SIZE 10005

char operatorStack[MAX_SIZE];
char operandStack[MAX_SIZE][MAX_SIZE];
int opTop = -1;
int operandTop = -1;

// Function to push operator to stack
void pushOperator(char op) {
    operatorStack[++opTop] = op;
}

// Function to pop operator from stack
char popOperator() {
    if (opTop >= 0) {
        return operatorStack[opTop--];
    }
    return '\0';
}

// Function to peek top operator
char peekOperator() {
    if (opTop >= 0) {
        return operatorStack[opTop];
    }
    return '\0';
}

// Function to push operand to stack
void pushOperand(char* operand) {
    strcpy(operandStack[++operandTop], operand);
}

// Function to pop operand from stack
void popOperand(char* result) {
    if (operandTop >= 0) {
        strcpy(result, operandStack[operandTop--]);
    }
}

// Function to get precedence of operators
int getPrecedence(char op) {
    if (op == '^') return 4;
    if (op == '*' || op == '/') return 3;
    if (op == '+' || op == '-') return 2;
    return 1;
}

// Function to check if character is operator
int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

// Function to check if character is operand (A-Z, a-z, 0-9)
int isOperand(char c) {
    return (isalnum(c));
}

// Function to validate parentheses
int validateParentheses(char* expression) {
    int count = 0;
    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] == '(') count++;
        else if (expression[i] == ')') {
            count--;
            if (count < 0) return 0;
        }
    }
    return count == 0;
}

// Function to process operator
void processOperator(char op) {
    char operand1[MAX_SIZE], operand2[MAX_SIZE];
    char result[MAX_SIZE];
    
    // Pop two operands
    popOperand(operand2);
    popOperand(operand1);
    
    // Create prefix expression: operator + operand1 + operand2
    sprintf(result, "%c%s%s", op, operand1, operand2);
    
    // Push result back
    pushOperand(result);
}

// Function to convert infix to prefix
void infixToPrefix(char* expression, char* result) {
    int len = strlen(expression);
    int i;
    
    // Reset stacks
    opTop = -1;
    operandTop = -1;
    
    // Process expression from left to right
    for (i = 0; i < len; i++) {
        char c = expression[i];
        
        // Skip spaces
        if (c == ' ') continue;
        
        if (isOperand(c)) {
            // Operand: push to operand stack
            char temp[2] = {c, '\0'};
            pushOperand(temp);
        }
        else if (c == '(') {
            // Left parenthesis: push to operator stack
            pushOperator(c);
        }
        else if (c == ')') {
            // Right parenthesis: process until '('
            while (opTop >= 0 && peekOperator() != '(') {
                char op = popOperator();
                processOperator(op);
            }
            // Pop the '('
            if (opTop >= 0) {
                popOperator();
            }
        }
        else if (isOperator(c)) {
            // Operator: process operators with higher or equal precedence
            while (opTop >= 0 && peekOperator() != '(' && 
                   getPrecedence(peekOperator()) > getPrecedence(c)) {
                char op = popOperator();
                processOperator(op);
            }
            pushOperator(c);
        }
        else {
            // Invalid character
            strcpy(result, "Invalid input");
            return;
        }
    }
    
    // Process remaining operators
    while (opTop >= 0) {
        char op = popOperator();
        if (op == '(' || op == ')') {
            strcpy(result, "Invalid input");
            return;
        }
        processOperator(op);
    }
    
    // The final result should be in operand stack
    if (operandTop == 0) {
        strcpy(result, operandStack[0]);
    } else {
        strcpy(result, "Invalid input");
    }
}

int main() {
    int n;
    char expression[MAX_SIZE];
    char result[MAX_SIZE];
    
    // Read number of expressions
    if (scanf("%d", &n) != 1 || n < 1 || n > 100) {
        printf("Invalid input\n");
        return 0;
    }
    
    // Clear input buffer
    getchar();
    
    // Process each expression
    for (int i = 0; i < n; i++) {
        // Read expression
        if (fgets(expression, sizeof(expression), stdin) == NULL) {
            printf("Invalid input\n");
            continue;
        }
        
        // Remove newline
        int len = strlen(expression);
        if (len > 0 && expression[len-1] == '\n') {
            expression[len-1] = '\0';
            len--;
        }
        
        // Validate expression length
        if (len > 10000) {
            printf("Invalid input\n");
            continue;
        }
        
        // Validate parentheses
        if (!validateParentheses(expression)) {
            printf("Invalid input\n");
            continue;
        }
        
        // Convert to prefix
        infixToPrefix(expression, result);
        
        // Output result
        printf("%s\n", result);
    }
    
    return 0;
}