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

#define MAX 10000

// Stack for operators/parentheses
char stack[MAX];
int top = -1;

// Stack for prefix
char prefixStack[MAX][MAX];
int ptop = -1;

// Check precedence
int precedence(char ch) {
    switch(ch) {
        case '^': return 3;
        case '*': case '/': return 2;
        case '+': case '-': return 1;
        default: return 0;
    }
}

// Push to stack
void push(char ch) { stack[++top] = ch; }
char pop() { return stack[top--]; }
char peek() { return (top == -1 ? '\0' : stack[top]); }

// Push to prefix stack
void ppush(char* str) { strcpy(prefixStack[++ptop], str); }
char* ppop() { return prefixStack[ptop--]; }

// Check for valid character
int is_valid_char(char ch) {
    return (isalnum(ch) || ch == '(' || ch == ')' || ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}

// Check parentheses balance
int is_balanced(char* expr) {
    int count = 0;
    for(int i = 0; expr[i]; i++) {
        if(expr[i] == '(') count++;
        else if(expr[i] == ')') count--;
        if(count < 0) return 0;
    }
    return count == 0;
}

// Convert infix to prefix
void infixToPrefix(char* expr) {
    int len = strlen(expr);
    // Reverse infix expression
    char rev[MAX], pre[MAX];
    int j = 0;
    for(int i = len-1; i >= 0; i--) {
        if(expr[i] == '(') rev[j++] = ')';
        else if(expr[i] == ')') rev[j++] = '(';
        else rev[j++] = expr[i];
    }
    rev[j] = '\0';

    top = -1;
    ptop = -1;
    for(int i = 0; rev[i]; i++) {
        char ch = rev[i];
        if(isalnum(ch)) {
            char op[2] = {ch, '\0'};
            ppush(op);
        }
        else if(ch == '(') {
            push(ch);
        }
        else if(ch == ')') {
            while(top != -1 && peek() != '(') {
                char op1[MAX], op2[MAX], op3[MAX];
                strcpy(op1, prefixStack[ptop--]);
                strcpy(op2, prefixStack[ptop--]);
                char temp[MAX] = {pop(), '\0'};
                snprintf(op3, MAX, "%s%s%s", temp, op1, op2);
                ppush(op3);
            }
            pop(); // remove '('
        }
        else { // Operator
            while(top != -1 && precedence(peek()) > precedence(ch)) {
                char op1[MAX], op2[MAX], op3[MAX];
                strcpy(op1, prefixStack[ptop--]);
                strcpy(op2, prefixStack[ptop--]);
                char temp[MAX] = {pop(), '\0'};
                snprintf(op3, MAX, "%s%s%s", temp, op1, op2);
                ppush(op3);
            }
            push(ch);
        }
    }
    // Pop remaining
    while(top != -1) {
        char op1[MAX], op2[MAX], op3[MAX];
        strcpy(op1, prefixStack[ptop--]);
        strcpy(op2, prefixStack[ptop--]);
        char temp[MAX] = {pop(), '\0'};
        snprintf(op3, MAX, "%s%s%s", temp, op1, op2);
        ppush(op3);
    }
    // Print prefix (reverse)
    int plen = strlen(prefixStack[ptop]);
    for(int i = plen-1; i >= 0; i--) printf("%c", prefixStack[ptop][i]);
    printf("\n");
}

int main() {
    int n;
    scanf("%d\n", &n);
    char expr[MAX];
    for(int i = 0; i < n; i++) {
        fgets(expr, MAX, stdin);
        expr[strcspn(expr, "\n")] = '\0'; // Remove newline
        int valid = 1;
        for(int j = 0; expr[j]; j++) {
            if(!is_valid_char(expr[j])) { valid = 0; break; }
        }
        if(!valid || !is_balanced(expr)) {
            printf("Invalid input\n");
        } else {
            infixToPrefix(expr);
        }
    }
    return 0;
}