Fake Photo

Zhang3 has made a fake photo by Photoshop, and published it on the Internet.

However, there are $n$ watches in the photo, showing different times. We assume that every watch has two hands: the hour hand and the minute hand, both moves at a uniform speed.

Someone pointed out the problem of the watches. Then everyone began to doubt that it's a fake photo. To respond, Zhang3 will announce that the photo is taken at time $x$, which is a time in a day. By choosing $x$ perfectly, she can make all of the watches look like showing time $x$, with a small error. For example, if there are two watches showing $\text{12:30:00}$ and $\text{02:40:00}$ respectively, she can choose $x = \text{01:35:00}$ as if both watches are showing time $x$.

Specifically, we define the error of a hand of a watch as the angle between its actual location and its ideal location, where the ideal location is the correct location to show time $x$. In the example above, the first watch shows $\text{12:30:00}$ and $x = \text{01:35:00}$, so the minute hand has an error of $30^\circ$ while the error of the hour hand is a little bit larger.

Please help Zhang3 choose such $x$ that the maximum error among all of the $2n$ hands is minimized. $x$ doesn't need to be an integer in seconds. Print the optimal error in degrees.

The first line of the input gives the number of test cases $T \; (1 \le T \le 100)$. $T$ test cases follow.

For each test case, the first line contains an integer $n \; (1 \le n \le 5 \times 10^4)$, the number of watches.

Then $n$ lines follow, the $i^\mathrm{th}$ of which contains a string of format $\text{HH:MM:SS} \; (0 \le \text{HH} \le 23, 0 \le \text{MM, SS} \le 59)$, describing the time the $i^\mathrm{th}$ watch is showing.

The sum of $n$ in all test cases doesn't exceed $10^5$.

For each test case, print a line with a real number $\alpha \; (0 \le \alpha \le 180)$, representing the answer is $\alpha ^\circ$.

Your answers should have absolute or relative errors of at most $10^{-6}$.

2
2
12:30:00
02:40:00
3
00:00:00
23:59:59
06:30:30

32.5
91.55

2020 Multi-University Training Contest 4