EIU Programming Practices and Exams

-        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 <= 100) - the number of testcases
• Each testcase includes:
  • The first line is a unique integer N (N is odd and N >= 3) – Number of elements.
  • The second line is an array containing N elements of 2 types:
    • Type 1: integer I (1<= I <= 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
7
5 6 2 + * 3 / 
Output:
13.333333