Description

Xiaoming needs to ride a bicycle through $n$ road segments every morning to get to class. The length of the $i$-th segment is $w_i (m)$, and the speed limit is $s_i (m/s)$ (the riding speed on the road cannot exceed the speed limit). The maximum absolute value of acceleration is $a_i (m/s^{2})$ (he can either speed up or slow down). The initial speed is $0 (m/s)$. Your task is to compute the minimum time for Xiaoming to pass these $n$ segments.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

Then follow $T$ test cases, each in the following format:

Each test case contains $n+1$ lines.

The first line contains a positive integer $n$, representing that there are $n$ road segments.

The next $n$ lines each contain three positive integers $w_i, s_i, a_i$, representing the length, the speed limit, and the maximum absolute acceleration of the $i$-th segment, respectively.

Output Format

Output $T$ lines, corresponding to the answers for the $T$ test cases. That is, the minimum time Xiaoming needs to pass the $n$ road segments (your answer is accepted as long as the absolute error from the standard answer is within $10^{-5}$).

1
2
5 3 1
1 1 1

4.6904157598

Hint

For $60\%$ of the testdata: $0 < n \le 60$.

For $80\%$ of the testdata: $0 < n \le 80$.

For $100\%$ of the testdata: $0 < n \le 10^{2}, w_i, s_i, a_i \le 10$.

Translated by ChatGPT 5