Given two strings, s1 and s2, composed of only English alphabets (both upper and lower cases), find the alphabets that occur in both the strings. find the common alphabets (if any).
Note:
1. Upper and lower alphabets are different.
2. Don't print any duplicates, even if they exit multiple times.
 
Example 1:
Input: s1 = "tUvGH", s2 = "Hhev"
Output: Hv
Explanation: The common letter are H and v. 
Hence output is, "Hv".
Example 2:
Input: s1 = "aabb", s2 = "ccll"
Output: nil
Explanation: There is nothing common, hence
the output is "nil".
 
Your Task:
You don't need to read or print anything. Your task is to complete the function commom_String() which takes s1 and s2 as input parameter and returns the letters which are common in both the strings in string format. If there is nothing common then returns "nil". The string which is returned must contain all the capital letters followed by small letter in ascending order.
 
Expected Time Complexity:  O(max(|s1|, |s2|)
Expected Space Complexity: O(k) where k is constant.
 
Constraints:
1 ≤ |s1|, |s2| ≤ 1000

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(max(|s1|, |s2|)
Expected Auxiliary Space: O(k) where k is constant.

Starter code:
#User function Template for python3



class Solution:

	def common_String(self, s1, s2):

		# Code here

Solutions:
class Solution:

	def common_String(self, s1, s2):
		list1 = list(s1)
		list2 = list(s2)
		list3 = []
		ans = ''
		if len(list1) > len(list2):
			for i in list1:
				if i in list2:
					list3.append(i)
		elif len(list2) > len(list1):
			for i in list2:
				if i in list1:
					list3.append(i)
		elif len(list2) == len(list1):
			for i in list2:
				if i in list1:
					list3.append(i)
		if len(list3) > 0:
			list3.sort()
			for t in list3:
				if t not in ans:
					ans += t
			return ans
		else:
			return 'nil'


class Solution:

	def common_String(self, s1, s2):
		output = set(s1).intersection(set(s2))
		upper = []
		lower = []
		for char in output:
			if char.isupper():
				upper.append(char)
			else:
				lower.append(char)
		return ''.join(sorted(upper)) + ''.join(sorted(lower)) if output else 'nil'


class Solution:

	def common_String(self, s1, s2):
		r = ''.join(sorted(list(set([s for s in s1 if s in s2]))))
		return r if r != '' else 'nil'


class Solution:

	def common_String(self, s1, s2):
		s1 = set(s1)
		s2 = set(s2)
		ans = s1.intersection(s2)
		if len(ans) == 0:
			return 'nil'
		else:
			ans = sorted(ans)
			ans = ''.join(ans)
			return ans


class Solution:

	def common_String(self, s1, s2):
		x = set(s1)
		y = set(s2)
		z = x.intersection(y)
		if len(z) == 0:
			return 'nil'
		else:
			return ''.join(sorted(z))


class Solution:

	def common_String(self, s1, s2):
		result = ''
		if len(s1) < len(s2):
			for i in range(len(s1)):
				if s1[i] in s2 and s1[i] not in result:
					result += s1[i]
		else:
			for i in range(len(s2)):
				if s2[i] in s1 and s2[i] not in result:
					result += s2[i]
		if len(result) < 1:
			return 'nil'
		else:
			return ''.join(sorted(result))


class Solution:

	def common_String(self, s1, s2):
		r = ''
		for i in s1:
			if i in r:
				continue
			if i in s2:
				r += i
		if not r:
			return 'nil'
		return ''.join(sorted(r))


class Solution:

	def common_String(self, s1, s2):
		d1 = {}
		for i in s1:
			if i not in d1:
				d1[i] = 1
		d2 = {}
		for i in s2:
			if i not in d2:
				d2[i] = 1
		word = ''
		for i in d1:
			if i in d2:
				word += i
		cap = ''
		small = ''
		for i in word:
			if i.isupper():
				cap += i
			else:
				small += i
		cap = sorted(cap)
		small = sorted(small)
		ans = ''
		for i in cap:
			ans += i
		for i in small:
			ans += i
		if ans:
			return ans
		return 'nil'


class Solution:

	def common_String(self, s1, s2):
		ans = ''
		s1 = list(set(s1))
		s2 = list(set(s2))
		for i in s2:
			if i in s1:
				ans += i
		if len(ans) == 0:
			return 'nil'
		return ''.join(sorted(ans))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s1 = input()
		s2 = input()
		ob = Solution()
		ans = ob.common_String(s1, s2)
		print(ans)


class Solution:

	def common_String(self, s1, s2):
		s = {}
		for i in s1:
			s[i] = 1
		t = ''
		for i in s2:
			if i in s1 and i not in t:
				t += i
		if len(t) == 0:
			return 'nil'
		t = sorted(t)
		t = ''.join(t)
		return t
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s1 = input()
		s2 = input()
		ob = Solution()
		ans = ob.common_String(s1, s2)
		print(ans)


class Solution:

	def common_String(self, s1, s2):
		l = []
		ans = ''
		for i in s1:
			if i in s2:
				l.append(i)
		if len(l) > 0:
			l.sort()
			for ch in l:
				if ch not in ans:
					ans += ch
			return ans
		else:
			return 'nil'


class Solution:

	def common_String(self, s1, s2):
		result = ''
		if len(s1) < len(s2):
			s1 = list(s1)
		else:
			(s2, s1) = (s1, list(s2))
		s1.sort()
		for x in s1:
			if x in s2 and x not in result:
				result += x
		if result == '':
			return 'nil'
		return result


class Solution:

	def common_String(self, s1, s2):
		out = ''
		out_small = ''
		for i in s1:
			if i in s2:
				if 65 <= ord(i) <= 90:
					if i not in out:
						out += i
				elif i not in out_small:
					out_small += i
		return 'nil' if len(out + out_small) == 0 else ''.join(sorted(out) + sorted(out_small))


class Solution:

	def common_String(self, s1, s2):
		common = []
		for s2i in s2:
			if s2i in s1 and s2i not in common:
				common.append(s2i)
		if len(common) > 0:
			common = sorted(common)
			return ''.join(common)
		else:
			return 'nil'


class Solution:

	def common_String(self, s1, s2):
		k = ''
		for i in s1:
			if i in s2 and i not in k:
				k += i
		s = sorted(k)
		l = ''.join(s)
		if len(l) == 0:
			return 'nil'
		else:
			return l


class Solution:

	def common_String(self, s1, s2):
		d1 = {}
		d2 = {}
		similar = ''
		answer = ''
		for i in s1:
			if i not in d1:
				d1[i] = 1
		for i in s2:
			if i not in d2:
				d2[i] = 1
		if len(s1) > len(s2):
			for k in d2:
				if k in d1:
					similar += k
		else:
			for k in d1:
				if k in d2:
					similar += k
		if len(similar) > 0:
			for i in sorted(similar):
				answer += i
			return answer
		return 'nil'


class Solution:

	def common_String(self, s1, s2):
		c = set(s1)
		d = set(s2)
		e = c.intersection(d)
		a = list(e)
		if len(a) == 0:
			return 'nil'
		else:
			a.sort()
			b = ''
			for i in a:
				b += i
			return b


class Solution:

	def common_String(self, s1, s2):
		(c1, c2, res) = ([0] * 58, [0] * 58, '')
		for c in s1:
			c1[ord(c) - 65] = 1
		for c in s2:
			c2[ord(c) - 65] = 1
		for i in range(58):
			if c1[i] == 1 and c2[i] == 1:
				res += chr(i + 65)
		if res == '':
			return 'nil'
		return res


class Solution:

	def common_String(self, s1, s2):
		c = []
		for i in s2:
			if i in s1:
				if i not in c:
					c.append(i)
		if len(c) == 0:
			return 'nil'
		else:
			c.sort()
			x = ''.join(c)
			return x


class Solution:

	def common_String(self, s1, s2):
		s = ''
		for i in s1:
			if i in s2:
				if i not in s:
					s += i
		if s == '':
			s = 'nil'
		else:
			l = list(s)
			s = ''.join(sorted(s))
		return s


class Solution:

	def common_String(self, s1, s2):
		st = ''
		for i in range(max(len(s1), len(s2))):
			if len(s1) >= len(s2):
				if s2.find(s1[i]) != -1:
					st = st + s1[i]
			elif len(s1) < len(s2):
				if s1.find(s2[i]) != -1:
					st = st + s2[i]
		if len(st) == 0:
			return 'nil'
		st = set(st)
		st = sorted(st)
		return ''.join((i for i in st))


class Solution:

	def common_String(self, s1, s2):
		ss = ''
		for i in s2:
			if i in s1:
				if i not in ss:
					ss = ss + i
		if len(ss) > 0:
			s1 = ''
			b = ''.join(sorted(ss))
			for y in b:
				s1 += y
			return s1
		else:
			return 'nil'


class Solution:

	def common_String(self, s1, s2):
		s = ''
		for x in s2:
			if x in s1:
				if x not in s:
					s += x
		if len(s) > 0:
			s1 = ''
			a = list(s)
			b = sorted(a)
			for y in b:
				s1 += y
			return s1
		else:
			return 'nil'