Latest Valid Time

In this problem, you are given a list of time strings in the format HH:MM where some digits may be replaced with a '?' character. Your task is to determine the latest valid time possible by replacing each '?' with an appropriate digit (0-9). A valid time must satisfy the constraints $$0 \leq HH \leq 23$$ and $$0 \leq MM \leq 59$$. For example, given the input "2?:4?", the answer would be "23:49".

inputFormat

The first line of input contains an integer t (1 \leq t \leq 100), the number of test cases. Each of the following t lines contains a single string representing a time in the format HH:MM where some digits may be replaced by '?' characters.

outputFormat

For each test case, output the latest valid time possible on a new line.

3
2?:4?
?9:0?
??:??

23:49
19:09
23:59