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 12:30:00 and 02:40:00 respectively, she can choose x=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 12:30:00 and x=01:35:00, so the minute hand has an error of 30∘ 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≤T≤100). T test cases follow.
For each test case, the first line contains an integer n(1≤n≤5×104), the number of watches.
Then n lines follow, the ith of which contains a string of format HH:MM:SS(0≤HH≤23,0≤MM, SS≤59), describing the time the ith watch is showing.
The sum of n in all test cases doesn't exceed 105.
输出格式
For each test case, print a line with a real number α(0≤α≤180), representing the answer is α∘.
Your answers should have absolute or relative errors of at most 10−6.