RNG - Random Number Generator

no tags 

LoadingTime got a RNG (Random Number Generator) from his classmate several weeks ago. And he spent a lot of time study it. He found that RNG can generate a real number in range [-S, S] by executing following steps. First RNG generates n integer X1 ... Xn, the sum of which is equal to S. Then for each Xi, it generates a real number in range [-Xi, Xi] randomly. The output (a real number) of RNG will be the sum of the N generated real numbers. LoadingTime noticed that the distribution of the output was very interesting, and he wanted to know: for given N and X, what's the probability that the generated number is in range [A, B]. Could you help him?

Input

The first line contains an integer T representing the number of test cases.

For each test case, the first line contains three integers N, A, B (1 ≤ N ≤ 10, -100 ≤ AB ≤ 100) In the second line of the test case, you are given X1 ... Xn (1 ≤ Xi ≤ 10).

Output

For each test case, print a line contains a real number representing the probability as the problem required. It must be printed with exactly nine decimal places.

Example

Input:
5
1 -100 100
10
1 10 90
10
1 -20 5
10
2 -20 5
5 5
5 -5 10
1 2 3 4 5

Output:
1.000000000
0.000000000
0.750000000
0.875000000
0.864720052

hide comments
[Trichromatic] XilinX: 2011-07-17 03:57:50

My Ac program uses all double!!! What a joke!

JFF: 2011-07-17 03:57:50

after using all variables long double, I finally got ac!!!! what a joke!


Added by:Bin Jin
Date:2007-11-03
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:www.test-the-best.by