#1555 Bigital

53  1 s   128 MB

Description

My friend has a "bigital" clock. It displays 12-hour times in the form hh:mm:ss, using 6 columns of 1 watt light bulbs. Each column displays its value in binary, where a light is off to indicate a 0 and is on to indicate a 1. The clock can display all 12-hour times, from 01:00:00 to 12:59:59.
For example, 03:22:59 requires 8 lights to be on and looks like this:

0   0   0   0   0   1
0   0   0   0   1   0
0   1   1   1   0   0
0   1   0   0   1   1

Given tStart and tEnd, return the total number of watt seconds (3600 watt seconds = 1 watt hours) used by the clock in displaying all the times from tStart to tEnd, inclusive. The start and end time are less than 12 hours apart.

Input

﻿The first line of the input gives the number of test cases, T. T test cases follow, each test case consists one line, tStart and tEnd. tStart and tEnd will each contain exactly 8 characters. tStart and tEnd will each be in the form hh:mm:ss, where hh is between 01 and 12, inclusive, mm is between 00 and 59, inclusive, and ss is between 00 and 59, inclusive.

Output

Sample Output

3
12:00:00 12:00:00
12:59:59 01:00:00
12:01:00 12:00:00
Case #1: 2
Case #2: 11
Case #3: 302122