The following experiment is taking place. There are n points of a plane. Each point is moving with the uniform velocity. It is needed to determine the minimum circle which encloses all the points after each second of the experiment during the fixed time T.

Input

The first line of input contains the number t - the number of tests. Next comes the description of t tests. The first line of each test consists of two integers n - number of points and T - the duration of the experiment in seconds. The next n lines contain four integers separated by spaces x, y, vx, vy - initial coordinates and velocities of each point.

Constraints

1 <= t <= 10
1 <= n <= 2000
1 <= T <= 50
-100 <= x, y, vx, xy <= 100

Output

For each test case print T real numbers Ri for i from 1 to T rounded to two decimals after the point. Ri should be the radius of the minimal circle which encloses all the points.

Example

Input:
1
3 5
1 0 1 0
3 4 1 2
5 5 -2 -1

Output:
3.16
4.12
5.41
7.43
9.55