Flight Plan

You work for SLPC Airlines, a small airline company that has just found a critical bug in its flight planner. The bug causes flights to take paths that keep either latitude or longitude constant. For example, to route a plane from $(0, 0)$ to $(10, 10)$, the flight planner sends the plane from $(0, 0)$ to $(0, 10)$ on a path that keeps the latitude constant, and then from $(0, 10)$ to $(10, 10)$ on a path that keeps the longitude constant.

You want to know how much the company has been losing from this bug. As a first step, you have the latitude and longitude coordinates of various cities and want to compute the shortest possible flight distance between two cities and the bugged flight distance between them.

Assume that the Earth is a perfect sphere with a radius of $6{,}371$ km, and that SLPC aircraft fly at a negligible height above the surface of the Earth.

The bugged planner always takes a constant-latitude path first, keeping the starting latitude until it reaches the destination's longitude, and then a constant-longitude path to the destination. The constant-latitude leg goes around the circle of latitude the shorter way between the two longitudes. When the longitudes differ by exactly $180$ degrees, both ways have the same length.

Latitude and longitude

The latitude of a point on the Earth's surface is the angle between the plane of the equator and the line through the center of the Earth and that point. Latitudes range from $90^\circ$S (the South Pole) to $90^\circ$N (the North Pole).

The longitude of a point on the Earth's surface is the angle between a plane containing the Prime Meridian and a plane containing the North Pole, the point in question, and the South Pole. A meridian is half of a great circle from the North Pole to the South Pole, and the Prime Meridian is the meridian chosen to have longitude $0$. Longitudes range from $180^\circ$W to $180^\circ$E.

The first line contains a single integer $T$ ($1 \le T \le 10{,}000$), the number of test cases.

Each test case is a single line with four real numbers $a_1, b_1, a_2, b_2$ ($|a_1|, |a_2| \le 90$ and $|b_1|, |b_2| \le 180$). These numbers form a pair of latitude and longitude coordinates $(a_1, b_1)$ and $(a_2, b_2)$, in degrees. $(a_1, b_1)$ is the starting point and $(a_2, b_2)$ is the destination. A positive latitude is north of the equator, and a negative one is south. A positive longitude is east of the Prime Meridian, and a negative one is west.

For each test case, print one line with the shortest possible flight distance between the two points, followed by a space and the bugged flight distance between them. Both distances are in kilometers, rounded to exactly $8$ digits after the decimal point. A distance of $0$ is printed as 0.00000000.

In the first test case, the bugged flight planner happens to pick the best route between the two points. Both distances are exactly half of a great circle.

In the second test case, the bugged flight planner does not pick the best route, so the two answers differ.