Now judge is temporally not available for this problem. We are earnestly making necessary data. Sorry for the inconvenience.

In 21XX, human beings have successfully contacted extraterrestrial life forms. We have found several planets
where the intelligent life forms are living, and are enjoying interplanetary communication. *Vegetablia* is one of
such planets. Inhabitants of Vegetablia look like vegetables in the Earth, so we call them *Vegetablians* with full
of respects and familiarity towards them.

One day, Mr. Potato, one of your Vegetablian friends, told you that he has decided to get married to his girlfriend, Ms. Tomato. He said, gTo tell the truth, we have to do one thing before our marriage.h

gIn Vegetablia, there is a traditional practice of marriages. According to the practice, a man and a woman who
want to get married should separately make a trip around the Vegetablia and broaden their knowledge before
their wedding ceremony. Each of them starts a trip from a distinct point on the planet and he/she keeps going
forward until he/she reaches his/her start point. This practice is called *the vow of two rings* because paths of their
trips are just like two rings on the planet.h

gThere is a famous gossip on it: ea couple who met each other during the trip will become happy.f I hope that this will come true, but I realized that there are some cases where we can never meet depending on our starting points and starting directions. I really want to know whether we can possibly meet each other or not.h

As a good friend of Mr. Potato, you want to solve this problem for him. The Vegetablia planet is considered to be a unit sphere, and a path of the trip is expressed as a cutting surface of the sphere. Given two paths, your job is to find the coordinates of their intersecting points (if they exist).

The input consists of multiple test cases.

The first line of the input contains an integer which denotes the number of test cases.

Each test case consists of descriptions of two distinct circles on a sphere, each of which is represented by two
latitude/longitude coordinates. Two latitude/longitude coordinates *p*_{1} and *p*_{2} indicate a circle whose diameter
coincides with the line segment *p*_{1}-*p*_{2}. Each latitude/longitude coordinate is given as follows:

*lat* [N|S] *long* [E|W]

where *lat* and *long* are latitude and longitude of a point in degrees, respectively. The second (N or S) and fourth
token (E or W) specify to which hemisphere the point belongs. The values of *lat* and *long* satisfy 0 ≤ *lat* ≤ 90
and 0 ≤ *long* ≤ 180.

In each coordinate representation, you may assume that *p*_{1} and *p*_{2} never coincide, and the line segment *p*_{1}-*p*_{2} is
not the diameter of the unit sphere. You may also assume that values of *lat* and *long* in the input are integers. It
is guaranteed that there are two intersections if there are any intersections.

For each test case, output a line gCase *n*:h, where *n* is the test case number. After the line, output gNo intersec-
tion.h if two circles never intersect. Otherwise, output the coordinates of intersections with the same format as
input. The values should be printed with three digits after the decimal point. If the coordinates can be represented
in several ways, any of them suffice. All values should be printed without negative signs.

Output a blank line between each test case.

2 30 N 50 E 30 N 130 W 0 N 90 E 0 N 30 W 45 N 180 E 45 N 0 W 40 N 10 W 40 S 10 W

Case 1: 30.000 N 84.736 E 30.000 N 24.736 W Case 2: No intersection.

Source: ACM-ICPC Japan Alumni Group Practice Contest
, for World Finals, Tokyo, Japan, 2008-02-24

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/