Counting Chaos

Wolfgang Puck's rival, Emeril Lagasse (who is famous for his signature catchphrase “BAM!”), recently set the world culinary record in the category of smallest soufflé measuring in at a mere 2 cm! Wolfgang, not to be outdone, decided that he would set a culinary record of his own: the most symmetric marble cake in the world. This is clearly not an easy feat!

As we all know from Wolfgang's bestselling biography, he is a very superstitious chef. In his attempts to create the symmetric cake, he has vowed to remove the cake from the oven only at a palindromic time, i.e., a time that reads the same when read from left-to-right as right-to-left. Not including the current time, when is the next opportunity for Wolfgang to remove his cake?

Input Specification

On the first line of the input, you are given n, the number of attempts Wolfgang makes to make his symmetric cake. Each of the following n lines contains a string formatted as “HH:MM” indicating the current time on a twenty-four hour clock. (So 0 ≤ HH ≤ 23 and 0 ≤ MM ≤ 59 and “00:00” follows “23:59”.)

Output Specification

For each attempt, output a string indicating the next palindromic time (not including the current time) on a single line formatted as “hh:mm”. When determining if HH:MM is palindromic, ignore all leading zeroes in HH. If HH is zero, then ignore all leading zeroes in MM.

Sample Input

1. 3
2. 00:00
3. 23:30
4. 14:59

download as text file

Output for Sample Input

1. 00:01
2. 23:32
3. 15:51

download as text file