Recursive Function z

Time limit5sMemory limit256 MB

Summary

You evaluate the recursive function at n/m by tracing its arguments into a repeating cycle and solving the linear equations exactly.

Level: Medium7 of 10
Topics: Math, Graph, Recursion
Solved: No attempts yet

Problem

Let $t = n/m$ and define the function $z$ as follows.

z[t] = \begin{cases} \dfrac{a + (b + r t^2)\, z[-1 - 2t]}{r} & (t \le 0) \\ \dfrac{c + (d + r t^2)\, z[1 - 2t]}{r} & (t > 0) \end{cases}

Given integers $a$ , $b$ , $c$ , $d$ , $n$ , $m$ , $r$ , compute the value of $z[n/m]$ .

The parameters obey these bounds.

$1 \le n \le m \le 100$

$1 \le b \le r, \quad 1 \le d \le r, \quad 1 \le r \le 1000$

$1 \le a \le 1000, \quad 1 \le c \le 1000$

The definition always fixes $z[n/m]$ to a single value. Every parameter set in the input also satisfies $|z[n/m]| \le 10^4$ .

Input

The first line has the number of functions to evaluate, between 1 and 100 inclusive. Each of the following lines gives the integer parameters of one function, separated by spaces, in the order $n$ , $m$ , $a$ , $b$ , $c$ , $d$ , $r$ .

Output

For each parameter set print the value of $z[n/m]$ on its own line, rounded to exactly six digits after the decimal point. Print all six digits even when they are zero. If the rounded result is zero, print 0.000000 with no sign.

Examples2

Example 1

Input

3
1 1 1 1 1 1 1
2 3 1 2 3 4 10
2 3 5 6 7 8 9

Expected output

-1.000000
0.422581
4.111111

Example 2
Input
```
1
1 1 1000 1 1000 1 1000
```
Expected output
```
-1000.000000
```