Alice is a geeky girl. She has a lot of codes to execute but she always choose a lucky time to execute a code. 
Time is shown in 24 hour format as hh:mm:ss
Time is said to be lucky if all the 6 characters (except ':') are different.

Given the time when she completed the code find a lucky time to execute it so that Alice need to wait as little as possible.

Input :

First line contains T, the number of test cases. Each of next T lines contains time when she completes a code (in format described above).

Output:

For each test case, output a single line containing lucky time (in format described above)

Constraints :

0 ≤  hh < 24

0 ≤ mm < 60

0 ≤  ss  < 60

SAMPLE INPUT
3
00:00:00
12:59:59
23:59:59

SAMPLE OUTPUT
01:23:45
13:02:45
01:23:45
import sys
class test:
    def __init__(self):
        self.s = raw_input()
        self.ti = self.s.split(':')
        for i in range(0, 3):
            self.ti[i] = int(self.ti[i])
        if self.ti[0] > 23 or self.ti[1] > 59 or self.ti[2] > 59:
            raise Exception(str(self.ti[0]) + str(self.ti[1]) +
                    str(self.ti[2]))
        while self.lucky(self.ti) == False:
            self.ti[2] += 1
            if self.ti[2] == 60:
                self.ti[2] = 0
                self.ti[1] += 1
                if self.ti[1] == 60:
                    self.ti[1] = 0
                    self.ti[0] += 1
                    if self.ti[0] == 24:
                        self.ti[0] = 0
        ans = ""
        for i in range(0, 3):
            ans += str(self.ti[i]/10) + str(self.ti[i]%10)
            if i < 2:
            	ans += ":"
        print ans
    def lucky(self, tt):
        flag = []
        for i in range(0, 10):
            flag.append(0)
        for i in range(0, 3):
            flag[tt[i] / 10] += 1
            flag[tt[i] % 10] += 1
        for i in flag:
            if i > 1:
                return False
        return True
#sys.stdin = open('input-05.txt','r')
#sys.stdout = open('out-05.txt','w')
t = int(raw_input())
for i in range(0, t):
    obj = test()