
ZOJ Problem Set  3131
Digital clocks usually show the time in the form hh:mm:ss, where hh is a number between 00 and 23, and both mm and ss are numbers between 00 and 59. Removing the colons from hh:mm:ss will result in an integer hhmmss, which is called a clock integer. For example, the clock integer of 17:05:13 is 170513 and the clock integer of 00:07:37 is 737. You are given a time interval and you are to determine the number of clock integers in it that are multiples of 3. A time interval will be given by specifying its start and end time. For example, the time interval [00:59:58, 01:01:24] has a total of 1+1+60+25=87 clock integers, namely, 5958, 5959, 10000 through 10059, and 10100 through 10124. How many of them are multiples of 3? Note that a time interval that includes midnight may have a start time greater than its end time, as in [22:47:03, 01:03:24]. You may assume that a time interval is at least one second long and shorter than 24 hours. Write a program that can determine the number of multiples of 3 in a time interval. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of a single line that contains the start time and end time of a time interval, which are separated by a single space. Output Your program is to write to standard output. Each test case outputs exactly one line. Print the number of multiples of 3 among the clock integers in the time interval. The following shows a sample input with three test cases and its output. Sample Input 3 00:59:58 01:01:24 22:47:03 01:03:24 00:00:09 00:03:37 Sample Output 29 2727 70 Source: Asia Regional Contest Seoul 2006 