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

#define MAX 10000

typedef struct {
    char arr[MAX];
    int top;
} Stack;

void init(Stack *s) {
    s->top = -1;
}

void push(Stack *s, char c) {
    if (s->top < MAX - 1)
        s->arr[++(s->top)] = c;
}

char pop(Stack *s) {
    if (s->top >= 0)
        return s->arr[(s->top)--];
    return '\0';
}

char peek(Stack *s) {
    if (s->top >= 0)
        return s->arr[s->top];
    return '\0';
}

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

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

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

int isBalanced(char *expr) {
    Stack s;
    init(&s);
    for (int i = 0; expr[i]; i++) {
        if (expr[i] == '(')
            push(&s, '(');
        else if (expr[i] == ')') {
            if (pop(&s) != '(')
                return 0;
        }
    }
    return s.top == -1;
}

void reverse(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;
    }
}

void infixToPrefix(char *expr) {
    if (!isBalanced(expr)) {
        printf("Invalid input\n");
        return;
    }

    for (int i = 0; expr[i]; i++) {
        if (!isValidChar(expr[i])) {
            printf("Invalid input\n");
            return;
        }
    }

    reverse(expr);
    for (int i = 0; expr[i]; i++) {
        if (expr[i] == '(') expr[i] = ')';
        else if (expr[i] == ')') expr[i] = '(';
    }

    Stack stack;
    init(&stack);
    char result[MAX];
    int k = 0;

    for (int i = 0; expr[i]; i++) {
        char c = expr[i];
        if (isalpha(c)) {
            result[k++] = c;
        } else if (c == '(') {
            push(&stack, c);
        } else if (c == ')') {
            while (peek(&stack) != '(')
                result[k++] = pop(&stack);
            pop(&stack);
        } else if (isOperator(c)) {
            while (precedence(peek(&stack)) > precedence(c))
                result[k++] = pop(&stack);
             return 0;
        }
    }

    while (stack.top != -1)
        result[k++] = pop(&stack);

    result[k] = '\0';
    reverse(result);
    printf("%s\n", result);
}

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';
        infixToPrefix(expr);
    }
    return 0;
}