Blagoja Mladenov gr.5\
package com.blagoja;
import java.util.Scanner;

class Main {
    static boolean isLetter(String s) {
        char m = s.charAt(0);
        return m >= 'a' && m <= 'z';
    }

    static boolean isLeftOperator(String s) {
        char m = s.charAt(0);
        if (m == '|' || m == '&' || m == '?' || m == '<' || m == '>' || m == '+' || m == '-' || m == '*' || m == '/' || m == '%')
            return true;
        return false;
    }

    static boolean isRightOperator(String s) {
        char m = s.charAt(0);
        if (m == '!' || m == '~' || m == '^' || m == '=')
            return true;
        return false;
    }

    static int priority(String s) {
        char m = s.charAt(0);
        if (m == '=')
            return 1;
        if (m == '|')
            return 2;
        if (m == '&')
            return 3;
        if (m == '?')
            return 4;
        if (m == '<' || m == '>')
            return 5;
        if (m == '+' || m == '-')
            return 6;
        if (m == '*' || m == '/' || m == '%')
            return 7;
        if (m == '^')
            return 8;
        if (m == '!' || m == '~')
            return 9;
        if (m >= 'a' && m <= 'z')
            return 10;
        return 0;
    }

    static boolean isUnary(String s) {
        char m = s.charAt(0);
        if (m == '~' || m == '!')
            return true;
        return false;
    }

    static boolean isBinary(String s) {
        char m = s.charAt(0);
        if (m == '=' || m == '|' || m == '&' || m == '?' || m == '<' || m == '>' || m == '+' || m == '-' || m == '*' || m == '/' || m == '%' || m == '^')
            return true;
        return false;

    }

    public static void main(String[] args) {
        try{
        Scanner scanner = new Scanner(System.in);
       int n = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < n; i++) {

            String s = new String();
            s = "";
            String input = scanner.nextLine();
            boolean flag = false;
            for (int crt1 = 0; crt1 < input.length(); crt1++) {
                if (input.charAt(crt1) != ' ' && flag == false) {
                    flag = true;
                    s += input.charAt(crt1);
                    continue;
                }
                if (flag) {
                    s += input.charAt(crt1);
                }

            }
            if (s.length() == 0) {
                continue;
            }


            Stack stack = new Stack(s.length());
            String q = "" + s.charAt(0);

            if (q.equals("I")) {
                String tmp = "";
                int at = 0;
                boolean x = true;
                int counter = 0;
                for (int k = 0; k < s.length() && x == true; k++) {
                    String m = Character.toString(s.charAt(k));
                    if (isLetter(m))
                        counter++;
                }
                for (int l = 0; l < s.length() && x == true; l++) {
                    String m = Character.toString(s.charAt(l));
                    if (at == 0) {
                        if (m.charAt(0) == '(') {
                            at = 0;
                        } else {
                            if (isUnary(m)) {
                                at = 2;
                            } else {
                                if (isLetter(m)) {
                                    at = 1;
                                } else {
                                    if (isBinary(m))
                                        x = false;
                                    if (m.charAt(0) == ')')
                                        x = false;
                                }
                            }
                        }
                    } else {
                        if (at == 2) {
                            if (isUnary(m)) {
                                at = 2;
                            } else {
                                if (isLetter(m)) {
                                    at = 1;
                                } else {
                                    if (m.charAt(0) == '(') {
                                        at = 0;
                                    } else {
                                        if (isBinary(m)) {
                                            x = false;
                                        }
                                        if (m.charAt(0) == ')')
                                            x = false;
                                    }
                                }
                            }
                        } else {
                            if (at == 1) {
                                if (m.charAt(0) == ')') {
                                    at = 1;
                                } else {
                                    if (isBinary(m)) {
                                        at = 0;
                                    } else {
                                        if (isUnary(m))
                                            x = false;
                                        if (isLetter(m))
                                            x = false;
                                        if (m.charAt(0) == '(')
                                            x = false;
                                    }
                                }
                            }
                        }
                    }
                }
                if (at != 1)
                    x = false;
                for (int j = 0; j < s.length() && x == true; j++) {
                    String m = Character.toString(s.charAt(j));
                    if (isLetter(m)) {
                        tmp += m + " ";
                    }
                    if (m.charAt(0) == '(') {
                        stack.push("(");
                    }
                    if (m.charAt(0) == ')') {
                        if (!stack.isEmpty()) {
                            while (stack.top().charAt(0) != '(') {
                                tmp += stack.top() + " ";
                                stack.pop();
                                if (stack.isEmpty())
                                    break;
                            }
                        }
                        if (stack.isEmpty())
                            x = false;
                        stack.pop();
                    }
                    if (isLeftOperator(m)) {
                        if (!stack.isEmpty()) {
                            while (priority(stack.top()) >= priority(m)) {
                                tmp += stack.top() + " ";
                                stack.pop();
                                if (stack.isEmpty())
                                    break;
                            }
                        }
                        stack.push(m);
                    }
                    if (isRightOperator(m)) {
                        if (!stack.isEmpty()) {
                            while (priority(stack.top()) > priority(m)) {
                                tmp += stack.top() + " ";
                                stack.pop();
                                if (stack.isEmpty())
                                    break;
                            }
                        }
                        stack.push(m);
                    }
                }
                while (!stack.isEmpty() && x == true) {
                    tmp += stack.top() + " ";
                    if (stack.top().charAt(0) == '(')
                        x = false;
                    stack.pop();
                }
                String print = "";
                for (int r = 0; r < tmp.length() - 1; r++) {
                    print += Character.toString(tmp.charAt(r));
                }
                if (x == true)
                    System.out.println("ONP: " + print);
                else
                    System.out.println("ONP: error");
            }
            if (q.equals("O")) {
                String array[] = new String[256];
                int l = 0;
                for (int p = 0; p < s.length(); p++) {
                    String h = Character.toString(s.charAt(p));
                    if (isBinary(h) || isUnary(h) || isLetter(h)) {
                        array[l] = h;
                        l++;
                    }
                }
                stackArray st = new stackArray(l);
                stackArrayInt sP = new stackArrayInt(l);

                String tmp = "";
                int liczbaOperandow = 0, liczbaOperatorow = 0;
                boolean x = true;

                for (int j = 0; j < l; j++) {
                    if (!array[j].equals("(") && !array[j].equals(")"))
                        if (array[j].charAt(0) >= 'a' && array[j].charAt(0) <= 'z') {
                            st.push(array[j]);//element jest operandem
                            sP.push(priority(array[j]));
                            liczbaOperandow++;
                        } else {
                            tmp = "";

                            if (!array[j].equals("~") && !array[j].equals("!")) {
                                liczbaOperatorow++;
                                if (liczbaOperandow <= 1)
                                    x = false;
                                if (isLeftOperator(array[j])) {
                                    if (sP.top() <= priority(array[j]))
                                        tmp = "( " + st.pop() + " )";
                                    else
                                        tmp = st.pop();

                                    sP.pop();

                                    if (sP.top() < priority(array[j]))
                                        tmp = "( " + st.pop() + " )" + " " + array[j] + " " + tmp;
                                    else
                                        tmp = st.pop() + " " + array[j] + " " + tmp;

                                    sP.pop();
                                } else {
                                    if (isRightOperator(array[j])) {
                                        if (sP.top() < priority(array[j]))
                                            tmp = "( " + st.pop() + " )";
                                        else
                                            tmp = st.pop();

                                        sP.pop();

                                        if (sP.top() <= priority(array[j]))
                                            tmp = "( " + st.pop() + " )" + " " + array[j] + " " + tmp;
                                        else
                                            tmp = st.pop() + " " + array[j] + " " + tmp;

                                        sP.pop();
                                    }
                                }
                            } else {
                                if (sP.top() < priority(array[j]))
                                    tmp = array[j] + " ( " + st.pop() + " )";
                                else
                                    tmp = array[j] + " " + st.pop();

                                sP.pop();
                            }

                            st.push(tmp);
                            sP.push(priority(array[j]));
                        }
                }

                if (liczbaOperandow - 1 == liczbaOperatorow && x == true)
                    System.out.println("INF: " + st.pop());
                else
                    System.out.println("INF: error");
            }
        }
        }catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class Stack {
    int maxSize;
    String elem[];
    int top;

    public Stack(int size) {
        maxSize = size;
        elem = new String[maxSize];
        top = 0;
    }

    public void push(String x) {
        elem[top] = x;
        top++;
    }

    public void pop() {
        top--;
    }

    public String top() {
        return elem[top - 1];
    }

    public boolean isEmpty() {
        return (top <= 0);
    }
}
class stackArray
{
    private int maxSize;
    private String[] Elem;
    private int top;

    public stackArray(int size)
    {
        maxSize = size;

        Elem = new String[maxSize];
        top = maxSize;
    }

    public void push(String x)
    {
        if(!isFull())
            Elem[--top] = x;
    }

    public String pop()
    {
        if(isEmpty())
            return "";
        else
            return Elem[top++];
    }

    public String top()
    {
        if ( isEmpty() )
            return "";
        else
            return Elem[top];
    }

    public boolean isEmpty()
    {
        return (top == maxSize);
    }

    public boolean isFull()
    {
        return (top == 0);
    }
}

class stackArrayInt
{
    private int maxSize;
    private int[] Elem;
    private int top;

    public stackArrayInt(int size)
    {
        maxSize = size;

        Elem = new int[maxSize];
        top = maxSize;
    }

    public void push(int x)
    {
        if(!isFull())
            Elem[--top] = x;
    }

    public int pop()
    {
        if(isEmpty())
            return 0;
        else
            return Elem[top++];
    }

    public int top()
    {
        if ( isEmpty() )
            return 0;
        else
            return Elem[top];
    }

    public boolean isEmpty()
    {
        return (top == maxSize);
    }

    public boolean isFull()
    {
        return (top == 0);
    }
}