Problema número 483

Preparando el reloj

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Reloj en la fachada de un edificio

La tradición de despedir el año comiendo 12 uvas, una por cada campanada, impone mucha presión sobre los responsables de los relojes más emblemáticos de todo el país, alrededor de los que se agolpan miles de ciudadanos para comer el postre de Nochevieja sincronizados con su tañido.

Este año se ha jubilado Ana Da Campa, la relojera del pintoresco pueblo de Ribacastaña, y te han pedido a ti que te encargues del reloj. ¡Qué responsabilidad!

Como no te fías, o más bien no entiendes, el antiguo enjendro mecánico que hay en sus entrañas, has decidido digitalizar todo el proceso, y el primer paso es saber en qué momento exacto tendrá que sonar cada campanada. Desde el Ayuntamiento te han dicho en qué instante debe empezar la primera y la última de las 12 campanadas, y tienes que calcular los momentos de inicio de las demás, sabiendo que deben ir a intervalos regulares para no despistar a los vecinos y que tu primer año como responsable sea el último.

Como confías en que el proceso sea un éxito y el reloj pase a utilizarse en otras celebraciones, quieres poder hacerlo para cualquier número de campanadas y cualquier punto de inicio y fin del día.

Entrada

La entrada comenzará indicando el número de casos de prueba que habrá que procesar.

Cada uno está compuesto de dos líneas. La primera contiene dos horas, especificadas en el formato HH:MM:SS, con 0 ≤ HH < 24 y 0 ≤ MMSS < 60, e indicando el instante en el que deben comenzar a sonar la primera y última campanada respectivamente. Las dos horas serán distintas, pero podría ocurrir que la última sea "menor" que la primera, en cuyo caso se entenderá que ocurren al día siguiente de la primera.

La segunda línea contiene el número 2 ≤ N ≤ 86.400 de campanadas totales que deben sonar y el número 1 ≤ C ≤ N de la campanada cuyo instante de inicio quieres conocer.

Salida

Por cada caso de prueba se escribirá la hora en la que la campanada pedida debe comenzar, utilizando el formato HH:MM:SS con las mismas restricciones que en la entrada.

Se garantiza que todas las campanadas comienzan en un segundo exacto, por lo que no será necesario utilizar decimales.

Entrada de ejemplo

2
00:00:00 00:00:44
12 2
23:59:30 00:03:00
15 15

Salida de ejemplo

00:00:04
00:03:00