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 (x1, y1, z1) and you would like to reach (x2, y2, z2). 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?

Input

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 < 30000, 0 < n <= 1000. The absolute value of the x, y, z coordinates are smaller than 106. There are 5 input sets for 10 points.

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!

Example

Input:
5
2
0 0 0
0 0 0
4
0 0 0
0 0 0
100
2 -3 4
-4 5 6
100
2 -3 4
-4 5 7
1000
0 0 0
0 0 0

Output:
0.1666666667
0.0694444444
0.0001389381
0.0000000000
0.0000208505

Added by:Robert Gerbicz
Date:2009-09-07
Time limit:1s-1.148s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TCL WHITESPACE
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.