def same_seq(seq1, seq2):
	# Set placeholder values for larger and smaller sequences
	smaller = ""
	larger = ""
	# Find the larger sequence in the pair
	if (len(seq1) > len(seq2)):
		larger = seq1
		smaller = seq2
	else:
		larger = seq2
		smaller = seq1

	pair = ""
	mypairs = []
	for i in range (len(smaller)):
		temp = ""
		for j in range (i, len(smaller)):
			temp = temp + smaller [j]
			if (temp in larger):
				if (len(temp) > len(pair)):
					pair = temp
					mypairs = []
					mypairs.append(temp)
				elif (len(temp) == len(pair) and not temp in mypairs):
					mypairs.append(temp)
	# mypairs [] contains the largest pairs if any exist
	return (mypairs)




def get_next_pair (file):
	# Read the file line by line
	p1 = file.readline()
	p2 = file.readline()
	return p1, p2

def main():
	pairs_list = []
	# Open the external file
	f = open ('dna.txt' , 'r')
	num_pairs = int (f.readline())
	# Set a placeholding value for each pair in a sequence
	p1 = ""
	p2 = ""
	print ("Longest Common Sequences")
	print (" ")
	temp = ""
	for i in range (num_pairs):
		temp = print ("Pair",str(i+1)+":")
		p1, p2 = get_next_pair (f)
		pairs_list = same_seq (p1, p2)
		if (len(pairs_list) == 0):
			print ("No Common Sequence Found")
		else:
			for j in range (len(pairs_list)):
				print (pairs_list[j])
	print ()


main()