Time Zones

Prior to the late nineteenth century, timekeeping was a purely local matter. Each town set its clocks to noon when the sun reached its zenith, and the town clock or a clockmaker kept the "official" time. Citizens set their pocket watches and clocks to the town's time, and some enterprising people even offered a service of carrying an accurate watch from home to home to adjust clocks every week. Traveling between cities meant resetting one's pocket watch on arrival.

Once railroads began moving people rapidly across great distances, time became far more critical. In the early years the schedules were confusing because every stop ran on its own local time, so standardizing time was essential to operating the railroads efficiently.

In 1878, Canadian Sir Sandford Fleming proposed the system of worldwide time zones we still use today. He recommended dividing the world into twenty-four time zones, each 15 degrees of longitude apart. Because the earth rotates once every 24 hours through 360 degrees of longitude, it turns one twenty-fourth of a circle, or 15 degrees, each hour.

United States railroad companies adopted Fleming's standard time zones on November 18, 1883. In 1884 an International Prime Meridian Conference was held in Washington, D.C. to standardize time and choose the Prime Meridian. The conference selected the longitude of Greenwich, England as zero degrees and established 24 time zones based on it. Not every country switched immediately; although most U.S. states followed the Pacific, Mountain, Central, and Eastern zones by 1895, their use did not become mandatory until the Standard Time Act of 1918.

Today many countries use variations of Fleming's zones. All of China (which spans five zones) uses a single time zone, eight hours ahead of Coordinated Universal Time (UTC). Russia keeps its designated zones but stays permanently one hour ahead. Australia uses three zones, and its central zone is half an hour ahead of its designated zone. Several countries in the Middle East and South Asia also use half-hour zones.

Because time zones are based on segments of longitude, and lines of longitude converge at the poles, scientists at the North and South Poles simply use UTC; otherwise Antarctica would be split into 24 very thin time zones.

Time zones have standard capital-letter abbreviations, as follows:

UTC  Coordinated Universal Time
GMT  Greenwich Mean Time, defined as UTC
BST  British Summer Time, defined as UTC+1 hour
IST  Irish Summer Time, defined as UTC+1 hour
WET  Western Europe Time, defined as UTC
WEST Western Europe Summer Time, defined as UTC+1 hour
CET  Central Europe Time, defined as UTC+1
CEST Central Europe Summer Time, defined as UTC+2
EET  Eastern Europe Time, defined as UTC+2
EEST Eastern Europe Summer Time, defined as UTC+3
MSK  Moscow Time, defined as UTC+3
MSD  Moscow Summer Time, defined as UTC+4
AST  Atlantic Standard Time, defined as UTC-4 hours
ADT  Atlantic Daylight Time, defined as UTC-3 hours
NST  Newfoundland Standard Time, defined as UTC-3.5 hours
NDT  Newfoundland Daylight Time, defined as UTC-2.5 hours
EST  Eastern Standard Time, defined as UTC-5 hours
EDT  Eastern Daylight Saving Time, defined as UTC-4 hours
CST  Central Standard Time, defined as UTC-6 hours
CDT  Central Daylight Saving Time, defined as UTC-5 hours
MST  Mountain Standard Time, defined as UTC-7 hours
MDT  Mountain Daylight Saving Time, defined as UTC-6 hours
PST  Pacific Standard Time, defined as UTC-8 hours
PDT  Pacific Daylight Saving Time, defined as UTC-7 hours
HST  Hawaiian Standard Time, defined as UTC-10 hours
AKST Alaska Standard Time, defined as UTC-9 hours
AKDT Alaska Daylight Saving Time, defined as UTC-8 hours
AEST Australian Eastern Standard Time, defined as UTC+10 hours
AEDT Australian Eastern Daylight Time, defined as UTC+11 hours
ACST Australian Central Standard Time, defined as UTC+9.5 hours
ACDT Australian Central Daylight Time, defined as UTC+10.5 hours
AWST Australian Western Standard Time, defined as UTC+8 hours

Given the current time in one time zone, compute the time in another time zone.

The first line contains $N$, the number of test cases. Each of the next $N$ lines contains a time followed by two time zone abbreviations. The time is written in standard a.m./p.m. format, with midnight written as midnight and noon written as noon (because 12:00 a.m. and 12:00 p.m. are ambiguous). The given time is the current time in the first time zone.

For each test case, print on its own line the corresponding time in the second time zone, using the same format as the input. Print midnight for 12:00 a.m. and noon for 12:00 p.m.; otherwise print the time as h:mm a.m. or h:mm p.m., where the hour h has no leading zero and the minutes mm are written with exactly two digits.