D. Clever Plan
time limit per test
0.75 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is Rabbit. He hasn't Learnt in Books, but he can always think of a Clever Plan. This time he prepared the plan for Pooh on how to fool a Heffalump and get a lot of Hunny. Or is it a plan on how to fool themselves?

Consider $$$n$$$ pots of honey. Pooh randomly distributes pots between Heffalump and himself in such a way that both of them get at least one pot and all such distributions are equiprobable (the pots are indistinguishable, so there are $$$n - 1$$$ such distributions). Then they start to play the game.

The game consists of rounds, and it is over when either Heffalump or Pooh has no pots anymore. Each round is played using a fairly complex Rabbit's plan, so all we can say about a round is just three numbers: $$$p$$$, $$$q$$$, $$$r$$$ ($$$p + q + r = 1$$$). One of the following three events happens: either Heffalump takes one of Pooh's pots with probability $$$p$$$, Pooh takes one of Heffalump's pots with probability $$$q$$$, or nothing happens with probability $$$r$$$. And so on, every round.

Consider $$$i$$$ rounds were played, the game did not yet end, and distribution of pots between Heffalump and Pooh became exactly the same as it was before the first round. What is the probability of such an event?

Input

The first line contains the only integer $$$T$$$ — the number of test cases ($$$1 \leq T \leq 200$$$).

Each test case consists of three lines. The first line of each test case contains an integer $$$n$$$ — the number of pots ($$$3 \leq n \leq 26$$$). The second line of $$$t$$$-th test case contains three numbers: $$$p_t$$$, $$$q_t$$$, $$$r_t$$$ ($$$0.3 \leq p_t, q_t, r_t \lt 1$$$, $$$p_t + q_t + r_t = 1$$$). The probabilities are given with at most two digits after the decimal point. The third line contains an integer $$$k_t$$$ ($$$1 \leq k_t \leq 1600$$$) — the maximal number of rounds to play.

Output

For each test case, output $$$k_t$$$ lines; $$$i$$$-th of them should contain the probability of the event described above after $$$i$$$ rounds have passed. Answers should be given with relative error not exceeding $$$10^{-3}$$$.

Example
Input
1
3
0.3 0.3 0.4
5
Output
4.000000e-001
2.500000e-001
1.720000e-001
1.201000e-001
8.404000e-002