SP4785 HS09SHIP - Starship

You are traveling by starship and at any time you are always moving in one of **6** directions: forwards, backwards, up, down, left, or right. In other words, during every second, one of the three coordinates of your position changes by exactly one unit. Let us suppose that you are at (**x** $ _{1} $ ,**y** $ _{1} $ ,**z** $ _{1} $ ) and you would like to reach (**x** $ _{2} $ ,**y** $ _{2} $ ,**z** $ _{2} $ ). Unfortunately, yours is only a first generation starship, which means that all movements are completely random, so at every second you will be moving with probability 1/6 forwards/backwards/up/down/left/right. Could you compute the probability that we will be at the destination in the **n-**th second?

The first line contains integer **T**, representing the number of test cases. Each test case starts with a positive integer n, the next line gives the starting position of the starship, while the final one is the destination. It is known that: **T**

Output **T** lines, and in the **i**-th line give the required probability for the **i**-th test case. Use **10** digits after the decimal point!