"""
Sameer Pai
Senior Division
Bergen County Academies
"""

def pterm(t):
	ans = [0 ,0, 0, 0]
	if "~A" in t:
		ans[0] = 2
	elif "A" in t:
		ans[0] = 1
	if "~B" in t:
		ans[1] = 2
	elif "B" in t:
		ans[1] = 1
	if "~C" in t:
		ans[2] = 2
	elif "C" in t:
		ans[2] = 1
	if "~D" in t:
		ans[3] = 2
	elif "D" in t:
		ans[3] = 1

	return ans

def psquare(i, j):
	ans = [1, 1, 1, 1]
	if i > 1:
		ans[1] += 1

	if i == 0 or i == 3:
		ans[3] += 1

	if j > 1:
		ans[0] += 1

	if j == 0 or j == 3:
		ans[2] += 1

	return ans

def fits(t, s):
	for i in range(4):
		if t[i] != 0 and t[i] != s[i]:
			return False

	return True

def solve(s):
	gridstring = list(map(int, list(bin(int(s, 16))[2:].zfill(16))))
	grid = [gridstring[0:4], gridstring[4:8], gridstring[8:12], gridstring[12:16]]
	ans = ""
	"""exprs = [
	([(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 0), (1, 3)], "B"), 
	([(2, 0), (2, 1), (2, 2), (2, 3), (1, 1), (1, 2), (1, 0), (1, 3)], "D"),
	([(2, 0), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 0), (3, 3)], "~B"),
	([(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)], "A"),
	([(0, 2), (1, 2), (2, 2), (3, 2), (0, 1), (1, 1), (2, 1), (3, 1)], "C"),
	([(0, 2), (1, 2), (2, 2), (3, 2), (0, 3), (1, 3), (2, 3), (3, 3)], "~A"),
	([(0, 0), (0, 1), (0, 2), (0, 3), (3, 1), (3, 2), (3, 0), (3, 3)], "~D"),
	([(0, 0), (1, 0), (2, 0), (3, 0), (0, 3), (1, 3), (2, 3), (3, 3)], "~C"),
	([(0, 0), (0, 1), (0, 2), (0, 3)], "B~D"),
	([(1, 1), (1, 2), (1, 0), (1, 3)], "BD"),
	([(2, 0), (2, 1), (2, 2), (2, 3)], "~BD"),
	([(3, 1), (3, 2), (3, 0), (3, 3)], "~B~D"),
	([(0, 0), (1, 0), (2, 0), (3, 0)], "A~C"),
	([(0, 1), (1, 1), (2, 1), (3, 1)], "AC"),
	([(0, 2), (1, 2), (2, 2), (3, 2)], "~AC"),
	([(0, 3), (1, 3), (2, 3), (3, 3)], "~A~C"),
	([(0, 0), (0, 1), (1, 0), (1, 1)], "AB"),
	([(0, 1), (0, 2), (1, 1), (1, 2)], "BC"),
	([(0, 2), (0, 3), (1, 2), (1, 3)], "~AB"),
	([(1, 0), (1, 1), (2, 0), (2, 1)], "AD"),
	([(1, 1), (1, 2), (2, 1), (2, 2)], "CD"),
	([(1, 2), (1, 3), (2, 2), (2, 3)], "~AD"),
	([(2, 0), (2, 1), (3, 0), (3, 1)], "A~B"),
	([(2, 1), (2, 2), (3, 1), (3, 2)], "~BC"),
	([(2, 2), (2, 3), (3, 2), (3, 3)], "~A~B"),]"""
	prec = [
	"B", "D", "~B", # adjacent full rows
	"A", "C", "~A", # adjacent full columns
	"~C", "~D", # adj end-rows, then end-columns
	"B~D", "BD", "~BD", "~B~D", # full rows
	"A~C", "AC", "~AC", "~A~C", # full columns
	"AB", "BC", "~AB", "AD", "CD", "~AD", "A~B", "~BC", "~A~B", # blocks of 4
	"B~C", "~CD", "~B~C", # 4 adj end-row
	"A~D", "C~D", "~A~D", # 4 adj end-column
	"~C~D", # ~C~D
	"AB~D", "BC~D", "~AB~D",
	"ABD", "BCD", "~ABD",
	"A~BD", "~BCD", "~A~BD", 
	"A~B~D", "~BC~D", "~A~B~D", # top to bottom double row X's
	"AB~C", "A~CD", "A~B~C", 
	"ABC", "ACD", "A~BC", 
	"~ABC", "~ACD", "~A~BC",
	"~AB~C", "~A~CD", "~A~B~C", # left to right double column X's
	"B~C~D", "B~CD", "~B~CD", "~B~C~D", # adj end-row X's
	"A~C~D", "AC~D", "~AC~D", "~A~C~D", # adj end-col X's
	"AB~C~D", "ABC~D", "~ABC~D", "~AB~C~D",
	"AB~CD", "ABCD", "~ABCD", "~AB~CD",
	"A~B~CD", "A~BCD", "~A~BCD", "~A~B~CD",
	"A~B~C~D", "A~BC~D", "~A~BC~D", "~A~B~C~D" # single X's
	]

	while sum(sum(l) for l in grid):
		for t in prec:
			good = True
			pt = pterm(t)
			for i in range(4):
				for j in range(4):
					if fits(pt, psquare(i, j)) and grid[i][j] == 0:
						good = False

			if good:
				ans += t + "+"
				for i in range(4):
					for j in range(4):
						if fits(pt, psquare(i, j)):
							grid[i][j] = 0


	return ans[:-1]


f = open("3sr_sampledata.txt", "r")
i = 1
while True:
	s = f.readline().strip()
	if not s:
		break
	print(str(i) + ".", solve(s))
	i += 1