Given two strings S1 and S2 print whether they contain any common subsequence (non empty) or not.
NOTE: Print 1 if they have a common subsequence (non empty) else 0.
Example 1:
Input: S1 = "ABEF" , S2 = "CADE"
Output: 1
Explanation: "A", "E", "AE" are in 
both S1 and S2.
Example 2:
Input: S1 = "ABCDE" , S2 = "FGHIJ"
Output: 0
Explanation: There is no common
subsequences .
Your Task:  
You dont need to read input or print anything. Complete the function commonSubseq() which takes S1 and S2 as input parameter and returns 1 if they have a common subsequence (non empty) else 0.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(K), Where K = Constant.
Constraints:
1<= |S1|=|S2| <=1000

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(K), Where K = Constant.

Starter code:
#User function Template for python3
class Solution:
    def commonSubseq (ob, S1, S2):
        # code here 

Solutions:
class Solution:

	def commonSubseq(ob, S1, S2):
		for i in S1:
			if i in S2:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		n = len(S1)
		c = 0
		for i in range(n):
			if S1[i] in S2:
				c += 1
		if c > 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		S1 = list(set(S1))
		S2 = list(set(S2))
		a = S1 + S2
		b = set(a)
		if len(a) == len(b):
			return 0
		else:
			return 1


class Solution:

	def commonSubseq(ob, S1, S2):
		a = len(S1)
		i = 0
		while i < a:
			if S1[i] in S2:
				return 1
			i = i + 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		return int(bool(set(S1).intersection(set(S2))))


class Solution:

	def commonSubseq(ob, S1, S2):
		d = {}
		for x in S1:
			if x not in d:
				d[x] = True
		for y in S2:
			if y in d:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		count = 0
		for ch in S1:
			if ch in S2:
				count += 1
		return 1 if count >= 1 else 0


class Solution:

	def commonSubseq(ob, S1, S2):
		s1 = S1.split()
		s2 = S2.split()
		for i in S1:
			if i in S2:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		p = set(S1) & set(S2)
		if len(p) == 0:
			return 0
		else:
			return 1


class Solution:

	def commonSubseq(ob, S1, S2):
		for i in range(len(S2)):
			if S1[i] in S2:
				return 1
				break
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		d = {}
		for x in S1:
			d[x] = 1
		for x in S2:
			if x in d:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		smaller_set = set()
		if len(S1) <= len(S2):
			smaller_string = S1
			larger_string = S2
		else:
			smaller_string = S2
			larger_string = S1
		for i in range(len(smaller_string)):
			smaller_set.add(smaller_string[i])
		for i in range(len(larger_string)):
			if larger_string[i] in smaller_set:
				return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2) = input().split()
		ob = Solution()
		print(ob.commonSubseq(S1, S2))


class Solution:

	def commonSubseq(ob, S1, S2):
		for i in S1:
			if i in S2:
				return 1
				break
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(S1, S2) = input().split()
		ob = Solution()
		print(ob.commonSubseq(S1, S2))


class Solution:

	def commonSubseq(ob, S1, S2):
		count = 0
		s_in = [-1]
		for i in range(len(S1)):
			if S1[i] in S2:
				if S2.index(S1[i]) > max(s_in):
					s_in.append(S2.index(S1[i]))
		if len(s_in) > 1:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		m = 0
		for i in S1:
			if i in S2:
				m = 1
				break
		if m == 1:
			return '1'
		else:
			return '0'


class Solution:

	def commonSubseq(ob, S1, S2):
		s = set(S1).intersection(set(S2))
		if len(s) > 0:
			return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		l = [0] * 26
		for i in S1:
			l[ord(i) - ord('A')] += 1
		for i in S2:
			if l[ord(i) - ord('A')] > 0:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		set1 = set(S1)
		set2 = set(S2)
		lst = set1 & set2
		return 0 if lst == set() else 1


class Solution:

	def commonSubseq(ob, S1, S2):
		lst1 = list(S1)
		lst2 = list(S2)
		st = ''
		for i in range(len(S2)):
			if S2[i] in lst1:
				st += S2[i]
		ans = bool()
		for i in st:
			if i in lst1 and i in lst2:
				ans = True
		return 1 if ans == True else 0


class Solution:

	def commonSubseq(ob, S1, S2):
		my_list = []
		for i in S1:
			if i in S2:
				my_list.append(i)
		if len(my_list) != 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		s = set()
		for i in range(0, len(S1)):
			s.add(S1[i])
		for i in range(0, len(S2)):
			if S2[i] in s:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		flag = 0
		for i in range(len(S1)):
			if S1[i] in S2:
				flag = 1
			else:
				continue
		if flag == 1:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		s = ''
		for i in S1:
			if i in S2:
				s += i
		if len(s) > 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		s1 = []
		s2 = []
		count = 0
		for i in range(len(S1)):
			s1.append(S1[i])
		for j in range(len(S2)):
			s2.append(S2[j])
		for i in range(len(s1)):
			for j in range(len(s2)):
				if s1[i] == s2[j]:
					count += 1
		if count > 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		p = []
		q = []
		cnt = 0
		for i in S1:
			p.append(i)
		for j in S2:
			q.append(j)
		for i in p:
			if i in q:
				cnt = cnt + 1
		if cnt != 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		S1 = list(S1)
		S2 = list(S2)
		if len(set(S1).intersection(set(S2))) > 0:
			return 1
		else:
			return 0


class Solution:

	def commonSubseq(ob, a, b):
		for i in a:
			if i in b:
				return 1
		return 0


class Solution:

	def commonSubseq(ob, S1, S2):
		flag = 0
		for j in S1:
			if j in S2:
				flag = 1
				break
		return flag


from collections import defaultdict

class Solution:

	def commonSubseq(ob, s1, s2):
		n = len(s1)
		d = defaultdict(lambda : 0)
		for i in s1:
			d[i] = 1
		for i in s2:
			if d[i] == 1:
				return 1
		return 0