Description

You have to place N queens on an N-by-N chessboard in a way that no two queens attack each other.

The rule is that each row, column, and diagonal of the board contains exactly one queen.

Your mission is to compute how many possible ways to place N queens on that chessboard.

Input

An integer N that represents the size of chessboard and the number of queens.

where 1<=N<=10

Output

An integer that represents the number of possible placements of  N queens.

There is no need to add '\n' at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Infix notation: X + Y

• Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."

 

Prefix notation (also known as "Polish notation"): + X Y

• Operators are written before their operands. The expressions given above are equivalent to / * A + B C D

 

Now, please write a program to convert the given expressions from prefix to infix.

Input

The first line contains a positive integer N, indicating the number of testcases in this input.

In the following N lines, each line contains a prefix expression.

In each prefix expression, there is a space between numbers and operators, and operators and operators.

Output

Output the infix expression and its answer of each given prefix expression.

Note that

• There is a space between numbers and operators, and operators and operators.
• If the answer is integer, there is no need to print decimal point. Otherwise, you should print only one digit after the decimal point.
• You have to print a '\n' at the end of each ouput.
• Add a pair of parentheses to wrap around each operator and its operands.

Sample Input  Download

Sample Output  Download

Tags

Discuss