A PIN code is a string that consists of exactly $4$ digits. Examples of possible PIN codes: 7013, 0000 and 0990. Please note that the PIN code can begin with any digit, even with 0.

Polycarp has $n$ ($2 \le n \le 10$) bank cards, the PIN code of the $i$-th card is $p_i$.

Polycarp has recently read a recommendation that it is better to set different PIN codes on different cards. Thus he wants to change the minimal number of digits in the PIN codes of his cards so that all $n$ codes would become different.

Formally, in one step, Polycarp picks $i$-th card ($1 \le i \le n$), then in its PIN code $p_i$ selects one position (from $1$ to $4$), and changes the digit in this position to any other. He needs to change the minimum number of digits so that all PIN codes become different.

Polycarp quickly solved this problem. Can you solve it?


-----Input-----

The first line contains integer $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then test cases follow.

The first line of each of $t$ test sets contains a single integer $n$ ($2 \le n \le 10$) — the number of Polycarp's bank cards. The next $n$ lines contain the PIN codes $p_1, p_2, \dots, p_n$ — one per line. The length of each of them is $4$. All PIN codes consist of digits only.


-----Output-----

Print the answers to $t$ test sets. The answer to each set should consist of a $n + 1$ lines

In the first line print $k$ — the least number of changes to make all PIN codes different. In the next $n$ lines output the changed PIN codes in the order corresponding to their appearance in the input. If there are several optimal answers, print any of them.


-----Example-----
Input
3
2
1234
0600
2
1337
1337
4
3139
3139
3139
3139

Output
0
1234
0600
1
1337
1237
3
3139
3138
3939
6139

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

t=int(input())
for testcases in range(t):
    n=int(input())

    LIST=[input().strip() for i in range(n)]
    SET=set()

    ANS=0
    CHANGE=set()
    for i in range(n):
        if LIST[i] in SET:
            ANS+=1
            CHANGE.add(i)
        else:
            SET.add(LIST[i])

    ALIST=[]

    for i in range(n):
        if i in CHANGE:
            flag=0
            now=LIST[i]
            
            for j in range(4):
                for k in range(10):
                    x=now[:j]+str(k)+now[j+1:]

                    if x in SET:
                        continue
                    else:
                        ALIST.append(x)
                        SET.add(x)
                        flag=1
                        break
                if flag:
                    break

        else:
            ALIST.append(LIST[i])
    print(ANS)
    print("\n".join(ALIST))

    

    



t=int(input())
for nt in range(t):
    n=int(input())
    a=[None]*n
    tc=[]
    d=set()
    for i in range(n):
        a[i]=input()
        if a[i] in d:
            tc+=[i]
        d.add(a[i]);
    for i in tc:
        for j in range(10):
            if a[i][:3]+str(j) not in d:
                a[i]=a[i][:3]+str(j)
                d.add(a[i])
                break
    print(len(tc))
    for i in a:
        print(i)


t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    for i in range(n):
        a.append(input())

    added = set()
    everything = set(a)
    out = []
    res = 0
    for code in a:
        if code not in added:
            added.add(code)
            out.append(code)
        else:
            res += 1
            done = False
            for i in range(4):
                for d in range(9+1):
                    nw = code[:i] + str(d) + code[i+1:]
                    if nw not in everything:
                        added.add(nw)
                        everything.add(nw)
                        out.append(nw)
                        done = True
                        break
                if done: break
    print(res)
    print('\n'.join(out))


def solve():
    n = int(input())
    d = {}
    ss = [input() for i in range(n)]
    for s in ss:
        d[s] = d.get(s,0)+1
    ans = sum(i-1 for i in d.values())
    print(ans)
    used = set(d.keys())
    l = []
    for s in ss:
        if d[s] > 1:
            t = list(s)
            f = False
            for i in range(4):
                for j in range(10):
                    t[i] = str(j)
                    u = "".join(t)
                    if u not in used:
                        l.append(u)
                        used.add(u)
                        d[s] -= 1
                        f = True
                        break
                if f:
                    break
        else:
            l.append(s)
            used.add(s)
    print(*l, sep="\n")

t = int(input())
for i in range(t):
    solve()

for _ in range(int(input())):
	n = int(input())
	l = [int(input()) for a in range(n)]
	ans = 0
	for i in range(n):
		if l[i] in l[i+1:]:
			ans += 1
			while l[i] in l[i+1:] + l[:i]:
				l[i] += 1000
				l[i] %= 10000
	print(ans)
	for i in l:
		print("%04d" % i)


import sys
def I():
        return sys.stdin.readline().rstrip()

for _ in range(int(I())):
    n = int(I())
    c = 0
    l = [ I() for _ in range(n) ]
    r = []
    for s in l:
        if s in r:
            c += 1
            for i in range(10):
                sn = s[:-1] + chr(ord('0')+i) 
                if sn not in l and sn not in r:
                    s = sn
                    break
        r.append( s )
    print(c)
    for s in r:
        print(s)


t = int(input())
for i in range(t):
    n = int(input())
    p = []
    s = []
    d = {}
    for j in range(n):
        st = input()
        s.append(st)
        p.append(list(map(int, list(st))))
        if st in list(d.keys()):
            d[st].append(j)
        else:
            d[st] = [j]
    
    poss = [i for i in range(10)]
    for j in range(n):
        poss[p[j][0]] = -1
    rest = [x for x in poss if x != -1]
    r_i = 0
    res = 0
    for k in list(d.keys()):
        if len(d[k]) > 1:
            for r in d[k][1:]:
                p[r][0] = rest[r_i]
                r_i += 1
                res += 1
    print(res)
    for o in p:
        print("".join(map(str, o)))
    
    


def run_length_compress(string):
    string.append("@")
    n = len(string)

    begin = 0
    end = 1
    cnt = 1
    ans = []
    while True:
        if end >= n:
            break
        if string[begin] == string[end]:
            end += 1
            cnt += 1
        else: 
            ans.append((cnt, string[begin]))
            begin = end
            end = begin + 1
            cnt = 1
    
    return ans

t = int(input())
for _ in range(t):
    n = int(input())
    p = [input() for i in range(n)]
    set_ = set([])
    init_set = set([])
    for i in range(n):
        init_set.add(p[i])
    ans_num = 0
    ans = []
    for i in range(n):
        flag = False
        if p[i] not in set_ and p[i] in init_set:
            ans.append(p[i])
            set_.add(p[i])
            continue
        while True:
            if p[i] not in set_ and p[i] not in init_set:
                ans.append(p[i])
                set_.add(p[i])
                if flag:
                    ans_num += 1
                break
            else:
                p[i] = str((int(p[i][0])+1) % 10) + p[i][1:]
                flag = True
    print(ans_num)
    for i in ans:
        print(i)

t = int(input())

def change(p, dct):
    if dct[p] == 1:
        return [p, 0]
    for j in range(4):
        for i in range(10):
            nw = list(p[:])
            nw[j] = str(i)
            nw = ''.join(nw)
            if nw not in dct:
                return [nw, 1]

for _ in range(t):
    n = int(input())
    l = {}
    pins = []
    for i in range(n):
        s = input()
        pins.append(s)
        if s in l:
            l[s] += 1
        else:
            l[s] = 1
    res = []
    cnt = 0
    for p in pins:
        c, d = change(p, l)
        cnt += d
        l[p] -= 1
        if l[p] == 0:
            del l[p]
        if c not in l:
            l[c] = 1
        else:
            l[c] += 1
        res.append(c)
    print(cnt)
    for i in res:
        print(i)



t = int(input())

for _ in range(t):
    n = int(input())
    k = []
    for i in range(n):
        k.append(input())
    total = 0
    for i in range(n):
        count = 0
        for j in range(n):
            if k[i] == k[j]:
                count += 1
        if count > 1:
            temp = k[i]
            for a in ['0','1','2','3','4','5','6','7','8','9']:
                if a + k[i][1:] not in k:
                    k[i] = a + k[i][1:]
                    break
            if temp == k[i]:
                for a in ['0','1','2','3','4','5','6','7','8','9']:
                    if k[i][0] + a + k[i][2:] not in k:
                        k[i] = a + k[i][1:]
                        break
            total += 1
    print(total)
    for i in range(n):
        print(k[i])


for _ in range(int(input())):
	n=int(input())
	l=[]
	for i in range(n):
		l.append(input())
	ans1=0
	ans2=[None]*n
	for j in range(n):
		if l[j] not in ans2:
			ans2[j]=l[j]
	for j in range(n):
		if ans2[j]==None:
			for pos in range(4):
				for d in range(9):
					jd=l[j][:pos]+chr(ord('0')+d)+l[j][pos+1:]
					if jd not in ans2:
						ans1+=1
						ans2[j]=jd
						break
				else:
					continue
				break
	print(ans1)
	for i in ans2:
		print(i)

t=int(input())
for _ in range(t):
    n=int(input())
    vis=set()
    it=[input() for i in range(n)]
    ss={}
    ans=[]
    j=0
    for i in it:
        try:
        
            ss[i].append(j)
        except:
            ss[i]=[j]
        j+=1
    tot=0
    x=list(ss.keys())[:]
    for i in x:
        if len(ss[i])==1:
            continue
        for kk in ss[i][1:]:
            for jj in range(10):

                j=i
                j=j[:3]+str(jj)
                try:
                    x=ss[j]
                except:
                    tot+=1
                    ss[j]=[kk]
                    break
        ss[i]=[ss[i][0]]
    for i in ss:
        ans.append([i,ss[i][0]])
    
    ans.sort(key=lambda x:x[1])
    print(tot)
    for i in ans:
        print(i[0])
    
    
            
    
    
    


for _ in range(int(input())):
	n = int(input())

	ans = []

	ps = [input() for _ in range(n)]

	suf = {}

	for i in range(n):
		p = ps[i]
		s = p[1:]
		if s not in suf:
			suf[s] = [str(A) for A in range(10)]

		if p[0] in suf[s]:
			suf[s].remove(p[0])


	cnt = 0

	used = {}

	for i in range(n):
		p = ps[i]
		s = p[1:]

		if s in used and p[0] in used[s]:
			p = suf[s][-1] + s
			cnt += 1
			suf[s].pop()

		used.setdefault(s, set()).add(p[0])

		ans.append(p)

	print(cnt)
	print(*ans, sep = "\n")

t=int(input())
for i in range(t):
    n=int(input())
    a=dict()
    b=[]
    for i in range(n):
        c=input()
        a[c]=a.get(c,-1)+1
        b.append(c)
    print(sum(a.values()))
    rlb=list(range(len(b)))
    for i in rlb:
        v=b[i]
        if a.get(v,0)==0:
            print(v)
        else:
            v,vo=v[1:],v
            for i in range(10):
                if not str(i)+v in a:
                    a[str(i)+v]=0
                    a[vo]-=1
                    print(str(i)+v)
                    break


from math import *
from collections import *
import sys
sys.setrecursionlimit(10**9)

t = int(input())
for y in range(t):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(input()))
	
	ch = 0
	for i in range(n):
		key = 0
		for j in range(n):
			if(j == i): continue
			if(a[i] == a[j]):
				key = 1
				break
		if(key == 1):
			#print(a[i])
			for j in range(4):
				b = a[i][::]
				flag = 0
				for k in range(10):
					b[j] = str(k)
					if(b not in a):
						ch += 1
						a[i][::] = b
						flag = 1 
						break
				if(flag == 1):
					break
	print(ch)
	for i in a:
		print("".join(i))


from collections import Counter

DIGS = "0123456789"

t = int(input())

for _ in range(t):
	n = int(input())
	P = [input() for _ in range(n)]
	
	print(sum(v-1 for v in Counter(P).values()))
	
	for i in range(len(P)):
		if P[i] in P[:i]:
			for dig in DIGS:
				if (dig + P[i][1:]) not in P:
					P[i] = dig + P[i][1:]
					break
	
	for p in P:
		print(p)

a = int(input())
for i in range(a):
    n = int(input())
    l = []
    ls = []
    for i in range(n):
        k = input()
        l.append(k)
        ls.append(k)
    d = list(set(l))
    a = [[0 for i in range(11)] for j in range(5)]
    for i in range(len(d)):
        for j in range(4):
            a[j][int(d[i][j])] = 1
    f = set()
    ans = 0
    ansl = []
    for i in l:
        if i in f:
            r = 0
            ik = 0
            for j in range(10):
                if a[0][j] == 0:
                    a[0][j] = 1
                    r = 1
                    ik = j
                    break
            ansl.append(str(ik) + i[1:])
            ans += 1
            if r == 0:
                r = 0
                ik = 0
                for j in range(10):
                    if a[1][j] == 0:
                        a[1][j] = 1
                        r = 1
                        ik = j
                        break
                ansl.append(i[0] + str(ik) + i[2:])
                ans += 1  
                if r == 0:
                    r = 0
                    ik = 0
                    for j in range(10):
                        if a[2][j] == 0:
                            a[2][j] = 1
                            r = 1
                            ik = j
                            break
                    ansl.append(i[0:2] + str(ik) + i[3:])
                    ans += 1 
                    if r == 0:
                        r = 0
                        ik = 0
                        for j in range(10):
                            if a[3][j] == 0:
                                a[3][j] = 1
                                r = 1
                                ik = j
                                break
                        ansl.append(i[0:-1] + str(ik))
                        ans += 1                     
        else:
            f.add(i)
            ansl.append(i)
    print(ans)
    for i in ansl:
        print(i)



t = int(input())
for i in range(t):
    n = int(input())
    cards = list()
    cou = 0
    for j in range(n):
        cards.append(input())
    br = False
    for j in range(n):
        br = False
        if cards.count(cards[j]) > 1:
            for k in range(4):
                for m in range(10):
                    temp = list(cards[j])
                    temp[k] = str(m)
                    temp = "".join(temp)
                    if temp not in cards:
                        cards[j] = temp
                        cou += 1
                        br = True
                        break
                if br:
                    break
    print(cou)
    print(*cards, sep="\n")


t=int(input())
for i in range(t):
  dc = {}
  n=int(input())
  arr=[]
  out = 0
  hm = {}
  arr2 = []
  for i in range(n):
    tem=input()
    arr2.append(tem)
    if tem in dc:
      dc[tem]+=1
      out+=1
    else:
      dc[tem]=1
      arr.append(tem)
      hm[tem] = [tem]
  arr.sort()
  cur = 0
  for i in range(len(arr)):
    for j in range(dc[arr[i]]-1):
      cur = '0'
      trun = arr[i][:3]
      while trun+cur in dc:
        cur = chr(ord(cur)+1)
      dc[trun+cur] = 1
      hm[arr[i]].append(trun+cur)
  print(out)
  for i in range(len(arr2)):
    dc[arr2[i]] -= 1
    arr2[i] = hm[arr2[i]][dc[arr2[i]]]
    print(arr2[i])

T = int(input())
for t in range(T):
    N = int(input())
    Ans = [0] * N
    coll = []
    V = set()
    for n in range(N):
        s = input().strip()
        if s in V:
            coll.append((s, n))
        Ans[n] = s
        V.add(s)
    for c, pos in coll:
        for i in range(4):
            tVal = int(c[i])
            for j in range(1, 10):
                c = c[:i] + str((tVal + j)%10) + c[i+1:]
                if c not in V:
                    V.add(c)
                    break
            else:
                c = c[:i] + str(tVal) + c[i+1:]
                continue
            break
        Ans[pos] = c
    print(len(coll), *Ans, sep = '\n')


def withZeros(m):
    t=str(m)
    if m<1000:
        t="0"+t
        if m<100:
            t="0"+t
            if m<10:
                t="0"+t
    return t
                    
q=int(input())
for query in range(q):
    n=int(input())
    r=[0 for i in range(n)]
    for i in range(n):
        r[i]=int(input())
    w=[r[i] % 1000 for i in range(n)]
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            if r[i]==r[j]:
                ans+=1
                for a in range(10):
                    if ((r[i]+a*1000+1000) % 10000) not in r:
                        r[i]=(r[i]+a*1000+1000) % 10000
                        break
    print(ans)
    for i in range(n):
        print(withZeros(r[i]))

"""
NTC here
"""
from sys import stdin, setrecursionlimit
setrecursionlimit(10**7)

def iin(): return int(stdin.readline())
 
 
def lin(): return list(map(int, stdin.readline().split()))

# range = xrange
# input = raw_input

def main():
    t=iin()
    while t:
        t-=1
        n=iin()
        ans=[]
        dc=set()
        ch=0
        todo=[]
        for _ in range(n):
            s=input()
            if s in dc:
                ans.append(s)
                todo.append(_)
            else:
                ans.append(s)
                dc.add(s)
        for j in todo:
            s=ans[j]
            ch+=1
            for i in range(10):
                if str(i)+s[1:] not in dc:
                    ans[j]=str(i)+s[1:]
                    dc.add(ans[j])
                    break
        
        print(ch)
        print(*ans,sep='\n')



            

main()


for _ in range(int(input())):
    n = int(input())
    arr = []
    for i in range(n):
        arr.append(input())

    p = '0123456789'
    ans = 0
    for i in range(n-1):
        if arr[i] in arr[i+1:]:
            ans +=1
            brr = []
            for j in range(n):
                brr.append(arr[j][0])
            for j in p:
                if j not in brr:
                    arr[i] = j + arr[i][1:]
                    break
    print(ans)       
    for i in arr:
        print(i)
    
            
    
        


t=int(input())
for ij in range(0,t):
	n=int(input())
	l=[]
	ans=0
	la=[]
	li=[]
	for i in range(0,n):
		s=input()
		la.append(s)
		if s in l:
			ans+=1
			li.append(i)
		else:
			l.append(s)
	print(ans)
	for i in li:
		s=la[i]
		for k in range(0,4):
			t=0
			for j in range(0,10):
				s1=s[:k]+str(j)+s[k+1:]
				if s1 not in l:
					l.append(s1)
					la[i]=s1
					t=1
					break
			if t==1:
				break
	for i in la:
		print(i)

3

import os
import sys


def main():
    T = read_int()
    for _ in range(T):
        N = read_int()
        c, ans = solve(N, [read_int() for _ in range(N)])
        print(c)
        for a in ans:
            print('{:04}'.format(a))


def solve(N, P):
    d = {}
    for p in P:
        if p not in d:
            d[p] = 0
        d[p] += 1

    c = 0
    ans = []
    for p in P:
        if d[p] == 1:
            ans.append(p)
            continue

        c += 1
        np = -1
        a = [p % 10, (p // 10) % 10, (p // 100) % 10, p // 1000]
        for i in range(4):
            for j in range(10):
                if a[i] == j:
                    continue
                orig = a[i]
                a[i] = j
                v = a[0] + a[1] * 10 + a[2] * 100 + a[3] * 1000
                if v not in d:
                    np = v
                    break
                a[i] = orig
            if np != -1:
                break

        ans.append(np)
        d[p] -= 1
        d[np] = 1

    return c, ans


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def __starting_point():
    main()

__starting_point()