WORLDPRO - World of Programs

“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>)=Hadamard Gate Applied to |0>and H(|1>) =Hadamard of |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 denoting the number of test cases. The description of Ttest cases follows. Each test case contains a single line of format "ax ay bx by n", where axaybxby are real numbers with at most 6 decimal places, denoting a qubit (ax + i ay)|0> + (bx + i by)|1>, and n (1 ≤ n ≤ 106) 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

Added by:mbk_live
Date:2019-01-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA JULIA PYTHON PYPY3 PYTHON3 SWIFT

hide comments
2021-05-04 20:03:24
Maybe I am wrong, but I think that the judge is incorrect. It should be fixed.
2020-07-29 23:01:27 Mitch Schwartz
Challenge section is for problems with a scoring system (you can look at any problem to see an example), and it seems this problem uses binary (AC or not AC) assessment, so it should be moved to classical.
2020-06-05 23:03:59
Could you please post the test cases and solutions? I believe that my approach is correct, but the judge says that it's not.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.