Problem H

If you know a little bit of quantum computers, this problem is:

Given n Hadamard Gates in series and an input qubit, predict the measurement of the output.

If you don't know about quantum computers, 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:

Due to linearity of quantum physics, the output for an arbitrary superposition a|0>+b|1> is aH(|0>)+bH(|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 contains the number of test cases T(T<=100). Each test case contains a single line of format "a₀ a₁ b₀ b₁ n", where a₀, a₁, b₀, b₁ are real numbers with at most 4 decimal places, denoting a qubit (a₀+a₁i)|0> + (b₀+b₁i)|1>, and n (1<=n<=10⁶) is the number of Hadamard Gates.

Output

For each test case, print the probability that the measurement is 0, to 6 decimal places.

Sample Input

2
1.0 0.0 0.0 0.0 1
0.017133 0.704420 0.410273 0.578943 1

Output for the Sample Input

Case 1: 0.500000
Case 2: 0.914848

Notes

(The following information is interesting, but will NOT help you solve this problem)

The act of measurement causes the system to change it state.

Take an electron as an example, if the outcome of the measurement is 0, then the new state of the system is |0> (the ground state), and if the outcome is 1, the new state is |1> (the excited state). This feature of quantum physics, that a measurement disturbs the system and forces it to choose (in this case ground or excited state), is another strange phenomenon with no classical analog.

You may conclude that quantum physics is completely different from, and unrelated to classical physics, but things are not that simple. Search the web for "Schr?dinger's cat". You'll get amazed.

Furthermore, take a look at this year (2012)'s Nobel Prize in Physics[1], which was awarded "for ground-breaking experimental methods that enable measuring and manipulation of individual quantum systems".

References

[1] "The Nobel Prize in Physics 2012". Nobelprize.org. 12 Nov 2012.http://www.nobelprize.org/nobel_prizes/physics/laureates/2012/