High School Programming League Problems Archive

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₁, y₁, z₁) and you would like to reach (x₂, y₂, z₂). 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 10⁶. 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