숫자 9

xkcd.com의 Randall Munroe는 전자레인지 키패드에서 숫자 9가 가장 적게 쓰이는 키라고 지적했습니다. 그 부담을 함께 나눠 봅시다.

전자레인지 시간은 네 개의 숫자 키로 입력하며 MM:SS 형식으로 표시됩니다. 앞의 두 자리는 분(minute) 필드, 뒤의 두 자리는 초(second) 필드이며, 각 필드는 00부터 99까지의 값을 가질 수 있습니다(따라서 초 필드가 59를 넘을 수도 있습니다). 입력 MM:SS가 나타내는 시간(초)은 $60 \times MM + SS$입니다.

원하는 조리 시간 $T$(초)가 주어질 때, 오차가 10% 미만이라는 조건을 지키면서 9 키를 최대한 많이 사용하는 네 자리 입력을 찾으세요. 입력이 나타내는 시간을 $T_9$라 하면, 이 입력이 허용되는 조건은

$10\,|T - T_9| < T$

입니다. 허용되는 입력들 중에서 9를 가장 많이 포함하는 것을 고르고, 개수가 같으면 오차 $|T - T_9|$가 가장 작은 것을, 그래도 같으면 사전순으로 가장 앞서는 MM:SS 문자열을 고릅니다.

풀이 예시: $T =$ 01:15(즉 $T = 75$초)일 때, $68$초부터 $82$초까지의 모든 시간이 10% 미만의 오차를 가집니다. 그중 00:69, 00:79, 01:09, 01:19가 9를 가장 많이(각각 한 개) 사용합니다. 이 가운데 오차가 가장 작은 것은 00:79와 01:19(오차 $4$)이며, 둘 중 사전순으로 더 앞서는 것은 00:79입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 줄에는 원하는 조리 시간이 MM:SS 형식으로 하나씩 주어지며, 각 자리 숫자는 0부터 9 사이입니다. 00:00 줄은 입력의 끝을 나타내며 처리하지 않습니다.

각 테스트 케이스마다 눌러야 할 네 개의 키를 MM:SS 형식으로 한 줄에 출력하세요.