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

#define MAX 10005

char stack[MAX];
int top = -1;

// Stack operations
void push(char c) {
    stack[++top] = c;
}

char pop() {
    if (top == -1) return '\0';
    return stack[top--];
}

char peek() {
    if (top == -1) return '\0';
    return stack[top];
}

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

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

// Reverse a string in place
void reverseString(char* str) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        char tmp = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = tmp;
    }
}

int isValidCharacter(char c) {
    return isalpha(c) || isOperator(c) || c == '(' || c == ')';
}

void infixToPrefix(char* infix) {
    int len = strlen(infix);
    char reversed[MAX * 2] = "";
    char result[MAX * 2] = "";
    top = -1;

    // Step 1: Reverse the infix expression and swap '(' <-> ')'
    for (int i = len - 1; i >= 0; i--) {
        if (infix[i] == '(')
            strncat(reversed, ")", 1);
        else if (infix[i] == ')')
            strncat(reversed, "(", 1);
        else
            strncat(reversed, &infix[i], 1);
    }

    int parenthesesBalance = 0;
    for (int i = 0; i < strlen(reversed); i++) {
        char c = reversed[i];

        if (!isValidCharacter(c) && !isspace(c)) {
            printf("Invalid input\n");
            return;
        }

        if (isalpha(c)) {
            strncat(result, &c, 1);
        } else if (c == '(') {
            push(c);
            parenthesesBalance++;
        } else if (c == ')') {
            parenthesesBalance--;
            if (parenthesesBalance < 0) {
                printf("Invalid input\n");
                return;
            }

            while (top != -1 && peek() != '(') {
                char op = pop();
                strncat(result, &op, 1);
            }

            if (top == -1) {
                printf("Invalid input\n");
                return;
            }

            pop();  // Remove '('
        } else if (isOperator(c)) {
            while (top != -1 && isOperator(peek()) &&
                   precedence(peek()) > precedence(c)) {
                char op = pop();
                strncat(result, &op, 1);
            }
            push(c);  // stack.push(c);
        } else if (isspace(c)) {
            continue;
        } else {
            printf("Invalid input\n");
            return;
        }
    }

    if (parenthesesBalance != 0) {
        printf("Invalid input\n");
        return;
    }

    while (top != -1) {
        char op = pop();
        if (op == '(' || op == ')') {
            printf("Invalid input\n");
            return;
        }
        strncat(result, &op, 1);
    }

    reverseString(result);

    printf("%s\n", result);
}

int main() {
    int n;
    scanf("%d", &n);
    getchar();  // Consume newline

    for (int i = 0; i < n; i++) {
        char expression[MAX * 2];
        fgets(expression, sizeof(expression), stdin);
        expression[strcspn(expression, "\n")] = 0;  // Remove trailing newline

        infixToPrefix(expression);
    }

    return 0;
}