Reverse Polish notation (RPN), is a mathematical notation in which operators follow their operands. The notation does not need any parentheses for as long as each operator has a fixed number of operands.

In RPN, the operators follow their operands. For example, to add ~3~ and ~4~ together, the expression is ~3 4 +~ rather than ~3 + 4~. The conventional notation expression ~3 - 4 + 5~ becomes ~3 4 - 5 +~ in reverse Polish notation: ~4~ is first subtracted from ~3~, then ~5~ is added to it.

You are given an array of strings tokens that represents an arithmetic expression in a RPN.

Your task is evaluate the expression. Return result that represents the value of the expression.

Input

• The first line contains an integer ~T~ (~T \leq 100~) - the number of testcases
• Each testcase includes:
  • The first line is a unique integer ~N~ (~N~ is odd and ~N \geq 3~) – Number of elements.
  • The second line is an array containing ~N~ elements of ~2~ types:
    • Type 1: integer ~I~ (~1 \leq I \leq 9~).
    • Type 2: ~O~ operator (~O~ belongs to { ~+~ , ~-~ , ~*~ , ~/~ })
• Surely input always has results.

Output

• A single number of the result of the problem, precision ~10^{-6}~.

Example Input 1

17
5 6 2 + * 3 / 

Example Output 1

13.333333