In geography, you have probably learned that locations on Earth are represented by latitude and longitude. Lines of latitude run in the same direction as the Equator. Latitudes start at the Equator, which is 0◦, representing the North-South direction. The range of latitudes is 180◦: from 90◦N (North Pole) to 0◦, and from 0◦ to 90◦S (South Pole). Lines of longitude run from North Pole to South Pole. Longitudes start at the meridian of Greenwich, which is 0◦, representing the East-West direction. The range of longitudes is 360◦: from 180◦E to 0◦, and from 0◦ to 180◦W. Therefore 180◦E is the same as 180◦W. Latitudes and longitudes use degrees as their unit. Degrees use minutes and seconds instead of plain decimal digits. 1 degree has 60 minutes, and 1 minute has 60 seconds. Only seconds have decimal digits. For example, Kingston, Ontario, is located at 44◦16′N, 76◦30′W, and Toronto, Ontario, is located at 43◦41′N, 79◦38′W. Assuming the Earth is a perfect sphere, the mean radius of the Earth is 6371.01 km. If you are given the latitude and longitude of two locations, can you find out the minimum walking distance between the two locations? Input The input starts with a line containing a number n, which is the number of pairs of locations, followed by n lines. Each line consists of the position of the two locations, separated by a space. Positions are in the format of: abcXdefY The first four represent the latitude. X is either the character ‘N’ or ‘S’, and the latitude is a◦b′c′′X (a degrees, b minutes, and c seconds). The next four represent the longitude. Y is either the character ‘E’ or ‘W’, and the longitude is d◦e′f′′Y . Each is separated by a space. a, b, d, e are integers, while c and f are floating point numbers with two decimal digits. Output The output consists of n lines, each lines contain a number with two decimal digits, in km, the minimum surface distance between the two locations on Earth. Note that you must travel on the surface of the Earth. You can assume that there is no mountain between the two places. Sample Input 2 44 16 0.00 N 76 30 0.00 W 43 41 0.00 N 79 38 0.00 W 22 18 12.34 N 114 10 56.78 E 49 11 43.21 N 123 10 7.65 W Sample Output 258.97 10255.47