Problem Description

Advanced courses in computer science often include many interesting optimization problems. The following optimization problem is not advanced, nor is it particularly interesting. You are to write a program to determine the minimum number of buttons a person must push to set their alarm clock. Assume the alarm clock has 7 buttons – hour-up, hour-down, tens-minute-up, and tens-minute-down, ones-minute-up, ones-minute-down, and am/pm. For example, continuously pushing the hour-up button will cause hour digit to go through the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, …. Pushing the hour-down button will cause the sequence to go in the reverse order. Pushing the tens-minute-up buttons cycles tens minute digit through the numbers 0, 1, 2, 3, 4, 5, 0, 1, … Pushing the ones-minute-up button cycles the one digit through the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, … Pushing the am/pm button causes toggles the am/pm indicator.

Input

The first line of input will contain an integer indicating the number of problems that need to be processed. Each line will contain two times – the first one the current time and the second one the desired time. All times will have the format: 1 or 2-digit hour; followed by a colon; followed by a 2-digit minute; followed by “am” or “pm”. A single space will separate the two times.

Output

Your program should produce one line of output for each problem using one of two formats: ”Going from 7:30am to 7:33am requires 3 pushes.” or “Going from 7:30am to 7:20am requires 1 push.”

6
7:30am 7:30am
7:30am 7:33am
7:30am 7:20am
7:30am 7:27am
7:30am 7:30pm
7:10am 7:50am

Going from 7:30am to 7:30am requires 0 pushes.
Going from 7:30am to 7:33am requires 3 pushes.
Going from 7:30am to 7:20am requires 1 push.
Going from 7:30am to 7:27am requires 4 pushes.
Going from 7:30am to 7:30pm requires 1 push.
Going from 7:10am to 7:50am requires 2 pushes.

Author

2008 ACM ICPC Regional hangzhou