Problem Description

Goffi has a connected undirected graph with \(n\) vertexes and \(m\) edges. Each edge has a weight, but with time going by, the weight will change. And at time \(t\), weight of \(i\)-th edge will be \(a_i + b_i \cdot t\).

Goffi wants to know the value of following formula:\[\Large\frac{\int_{0}^{T}{(\displaystyle\sum_{i=1}^{n}{F(i,t)})\mathrm{d}t}}{T}\]
Where \(F(i, t)\) is the minimum edge on the maximum capacity path between vertex 1 to vertex \(i\) (at time \(t\)). And the maximum capacity path between vertex 1 and \(i\) is the path for which the minimum edge on the path is maximum, among all such 1-\(i\) paths.

Input

The first line contains an integer \(C\) (\(1 \le C \le 50\)), indicating the number of test cases.

For each test case, the first line contains three integers \(n\), \(m\) and \(T\) (\(1 \le n \le 50, 0 \le m \le \min(\frac{n(n-1)}{2}, 100), 1 \le T \le 1000\)). In the next \(m\) lines, each contains four integers \(u_i\), \(v_i\), \(a_i\), \(b_i\) (\(1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le a_i, |b_i| \le 1000\)), which means this edge connects vertex \(u_i\) and \(v_i\).

From time 0 to time \(T\), \(a_i + b_i \cdot t\) is always larger than or equal to 0.

There's at most one edge between each pair of vertexes.

Output

For each case, output the result of the formula, rounded to 3 digits after decimal point.

1
4 5 2
1 2 2 1
2 3 3 1
1 4 1 1
4 3 5 1
1 3 4 1

14.000

Hint

F(1, t) = 0, F(2, t) = 3 + t, F(3, t) = 4 + t, F(4, t) = 4 + t.