“DNA in biology, superstrings in physics, and bits in computer science, it is all about programs. Programs rule Life, Universe and Everything.”  That is the claims of many scientists (e.g. David Deutsch, Leonid Levin) who support the digital physics theory.  One interesting thing about this theory is the fact that some supporters consider the universe as a big quantum computer that computes in an efficiently irreducible manner his own evolution. Some researchers argue that the programmer of such a program is outside the space and time limits.

Being in a big quantum computer, let us make some quantum measurements. Given “n” Hadamard Gates in series and an input qubit, predict the measurement of the output. If you still do not understand, keep on reading.

In quantum physics, superposition principle states that if a quantum system (e.g. an electron) can be in one of two states (denoted by |0> and |1>), it can also be in any linear superposition of those two states  a|0> + b|1>, where “a” and “b” are two complex numbers, normalized so that |a|² + |b|² = 1. Such a superposition, a|0> + b|1>, is the basic unit of encoded information in quantum computers, called qubit (pronounced "cubit").

An elementary quantum operation is analogous to an elementary gate like the AND or NOT gate in classical circuit. One of the most important examples is the Hadamard gate, denoted by H, which operates on a single qubit. On input |1> or |0>, it outputs:

H(|0>)=and H(|1>) =

Due to linearity of quantum physics, the output for an arbitrary superposition a |0> + b |1> is a H(|0>)+ b H(|1>).

However, the linear superposition is the private world of the quantum system. For us to get a glimpse of its state, we must make a measurement, and when we do so, we get a single bit of information: 0 or 1. If the state is a |0> + b |1>, then the outcome of the measurement is “0” with probability |a|² and “1” with probability |b|² (luckily we normalized so |a|²+|b|² = 1).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of Ttest cases follows. Each test case contains a single line of format "a_x a_y b_x b_y n", where a_x, a_y, b_x, b_y are real numbers with at most 6 decimal places, denoting a qubit (a_x + i a_y)|0> + (b_x + i b_y)|1>, and n (1 ≤ n ≤ 10⁶) is the number of Hadamard Gates.

Output

For each test case, print in a single line the probability that the measurement is 0, with a precision of 10^-6.

Example

Input:
2
1.0 0.0 0.0 0.0 1
0.017133 0.704420 0.410273 0.578943 1

Output:
0.500000
0.914848