E=enumerate
M=[(1,0),(-1,0),(0,-1),(0,1),(1,1),(-1,1),(-1,-1),(1,-1)]
def f(L):
 d,t={(x,y):v for x,r in E(L)for y,v in E(r)},[]
 for i in d.values():
  q={j for j in d if(j in t)+d[j]==i}
  while q:
   v=[*q][0];Q,s={v},{v}
   while Q:x,y=e=[*Q][0];Q-={e};l={V for X,Y in M if(V:=(x+X,y+Y))in d and(d[v]>=d[V])*~-(V in s)};Q={*Q,*l};s={*s,*l}
   q-=s;t+=[*s]*all(d.get((x+X,y+Y),-1)>d[(x,y)]or(x+X,y+Y)in[*t,*s]for x,y in s for X,Y in M)
 for x,y in t:L[x][y]='*'
 return'\n'.join(''.join(map(str,i))for i in L)
 
s1 = """
8888888888
5664303498
6485322898
5675373666
7875555787
"""
s2 = """
888
838
388
"""
s3 = """
77777
75657
75757
77677
77477
"""
s4 = """
599999
933339
936639
935539
932109
999999
"""
s5 = """
88888888
84482288
84452233
84482288
88888888
"""
def to_board(s):
	return [[*map(int,i)] for i in filter(None, s.split('\n'))]
 
print(f(to_board(s1)))
print('-'*40)
print(f(to_board(s2)))
print('-'*40)
print(f(to_board(s3)))
print('-'*40)
print(f(to_board(s4)))
print('-'*40)
print(f(to_board(s5)))

RT1lbnVtZXJhdGUKTT1bKDEsMCksKC0xLDApLCgwLC0xKSwoMCwxKSwoMSwxKSwoLTEsMSksKC0xLC0xKSwoMSwtMSldCmRlZiBmKEwpOgogZCx0PXsoeCx5KTp2IGZvciB4LHIgaW4gRShMKWZvciB5LHYgaW4gRShyKX0sW10KIGZvciBpIGluIGQudmFsdWVzKCk6CiAgcT17aiBmb3IgaiBpbiBkIGlmKGogaW4gdCkrZFtqXT09aX0KICB3aGlsZSBxOgogICB2PVsqcV1bMF07USxzPXt2fSx7dn0KICAgd2hpbGUgUTp4LHk9ZT1bKlFdWzBdO1EtPXtlfTtsPXtWIGZvciBYLFkgaW4gTSBpZihWOj0oeCtYLHkrWSkpaW4gZCBhbmQoZFt2XT49ZFtWXSkqfi0oViBpbiBzKX07UT17KlEsKmx9O3M9eypzLCpsfQogICBxLT1zO3QrPVsqc10qYWxsKGQuZ2V0KCh4K1gseStZKSwtMSk+ZFsoeCx5KV1vcih4K1gseStZKWluWyp0LCpzXWZvciB4LHkgaW4gcyBmb3IgWCxZIGluIE0pCiBmb3IgeCx5IGluIHQ6TFt4XVt5XT0nKicKIHJldHVybidcbicuam9pbignJy5qb2luKG1hcChzdHIsaSkpZm9yIGkgaW4gTCkKIApzMSA9ICIiIgo4ODg4ODg4ODg4CjU2NjQzMDM0OTgKNjQ4NTMyMjg5OAo1Njc1MzczNjY2Cjc4NzU1NTU3ODcKIiIiCnMyID0gIiIiCjg4OAo4MzgKMzg4CiIiIgpzMyA9ICIiIgo3Nzc3Nwo3NTY1Nwo3NTc1Nwo3NzY3Nwo3NzQ3NwoiIiIKczQgPSAiIiIKNTk5OTk5CjkzMzMzOQo5MzY2MzkKOTM1NTM5CjkzMjEwOQo5OTk5OTkKIiIiCnM1ID0gIiIiCjg4ODg4ODg4Cjg0NDgyMjg4Cjg0NDUyMjMzCjg0NDgyMjg4Cjg4ODg4ODg4CiIiIgpkZWYgdG9fYm9hcmQocyk6CglyZXR1cm4gW1sqbWFwKGludCxpKV0gZm9yIGkgaW4gZmlsdGVyKE5vbmUsIHMuc3BsaXQoJ1xuJykpXQoKcHJpbnQoZih0b19ib2FyZChzMSkpKQpwcmludCgnLScqNDApCnByaW50KGYodG9fYm9hcmQoczIpKSkKcHJpbnQoJy0nKjQwKQpwcmludChmKHRvX2JvYXJkKHMzKSkpCnByaW50KCctJyo0MCkKcHJpbnQoZih0b19ib2FyZChzNCkpKQpwcmludCgnLScqNDApCnByaW50KGYodG9fYm9hcmQoczUpKSk=