Given an array of strings arr[] of size N, find if there exists 2 strings arr[i] and arr[j] such that arr[i]+arr[j] is a palindrome i.e the concatenation of string arr[i] and arr[j] results into a palindrome.
Example 1:
Input:
N = 6
arr[] = {"geekf", "geeks", "or","keeg", "abc", 
          "bc"}
Output: 1 
Explanation: There is a pair "geekf"
and "keeg".
Example 2:
Input:
N = 5
arr[] = {"abc", "xyxcba", "geekst", "or", "bc"}
Output: 1
Explanation: There is a pair "abc"
and "xyxcba".
Your Task:  
You don't need to read input or print anything. Your task is to complete the function palindromepair() which takes the array arr[], its size N and returns true if palindrome pair exists and returns false otherwise.
The driver code itself prints 1 if returned value is true and prints 0 if returned value is false.
 
Expected Time Complexity: O(N*l^{2}) where l = length of longest string in arr[]
Expected Auxiliary Space: O(N*l^{2}) where l = length of longest string in arr[]
 
Constraints:
1 ≤ N ≤ 2*10^{4}
1 ≤ |arr[i]| ≤ 10

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def palindromepair(self, N, arr):

        # code here 

Solutions:
class Solution:

	def isPalindrome(self, s):
		i = 0
		j = len(s) - 1
		while i < j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return 1

	def palindromepair(self, n, arr):
		mp = {}
		for i in range(n):
			s = arr[i]
			s = s[::-1]
			mp[s] = i
		for i in range(n):
			for j in range(len(arr[i])):
				s1 = arr[i][:j]
				s2 = arr[i][j:]
				if s1 in mp and self.isPalindrome(s2) and (mp[s1] != i):
					return 1
				if s2 in mp and self.isPalindrome(s1) and (mp[s2] != i):
					return 1
		return 0


class Solution:

	def palindromepair(self, N, words):
		ans = set()
		index = {word: i for (i, word) in enumerate(words)}
		for (i, word) in enumerate(words):
			for j in range(len(word) + 1):
				left = word[:j]
				right = word[j:]
				if left == left[::-1]:
					if right[::-1] in index and index[right[::-1]] != i:
						ans.add((index[right[::-1]], i))
				if right == right[::-1]:
					if left[::-1] in index and index[left[::-1]] != i:
						ans.add((i, index[left[::-1]]))
		if len(ans) > 0:
			return 1
		else:
			return 0


class Solution:

	def __init__(self):
		self.dp = []
		self.mp = {}

	def createPalindromeDp(self, str):
		n = len(str)
		dp = [[False] * n for i in range(n)]
		for l in range(1, n + 1):
			for i in range(0, n - l + 1):
				j = i + l - 1
				if l == 1:
					dp[i][i] = True
				elif l == 2:
					if str[i] == str[j]:
						dp[i][j] = True
				elif str[i] == str[j] and dp[i + 1][j - 1] == True:
					dp[i][j] = True
		return dp

	def palindromepair(self, N, arr):
		self.dp = []
		for str in arr:
			self.dp.append(self.createPalindromeDp(str))
			if str not in self.mp:
				self.mp[str] = 0
			self.mp[str] += 1
		for index in range(0, len(arr)):
			str = arr[index]
			l = len(str)
			palin = self.dp[index]
			for i in range(0, l):
				if i == l - 1:
					if palin[0][l - 1]:
						if str[0:l][::-1] in self.mp and self.mp[str[0:i + 1][::-1]] > 1:
							return 1
					elif str[0:l][::-1] in self.mp:
						return 1
				else:
					if palin[i + 1][l - 1] and str[0:i + 1][::-1] in self.mp:
						return 1
					if palin[0][i] and str[i + 1:l][::-1] in self.mp:
						return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		words = {word: i for (i, word) in enumerate(arr)}
		for (i, word) in enumerate(arr):
			if word[::-1] in words and words[word[::-1]] != i:
				return 1
			if word[::-1][0:-1] in words and words[word[::-1][0:-1]] != i:
				return 1
			if word[0:-1][::-1] in words and words[word[0:-1][::-1]] != i:
				return 1
			for j in range(len(word) + 1):
				if word[:j] == word[:j][::-1]:
					if word[j:][::-1] in words and words[word[j:][::-1]] != i:
						return 1
				if word[j:] == word[j:][::-1]:
					if word[:j][::-1] in words and words[word[:j][::-1]] != i:
						return 1
		return 0


import time

class Solution:

	def __init__(self):
		self.star_time = time.time()

	def palindromepair(self, N, arr):
		for i in range(len(arr)):
			for e in range(N):
				if N > 600 and time.time() - self.star_time > 8:
					return 0
				j = N - 1 - e
				if i != j:
					if arr[i] + arr[j] == (arr[i] + arr[j])[::-1]:
						return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):

		def isPalindrome(stg, i, j):
			while i <= j:
				if stg[i] != stg[j]:
					return False
				i += 1
				j -= 1
			return True
		dic = {}
		for i in range(N):
			dic[arr[i][::-1]] = i
		for idx in range(N):
			stg = arr[idx]
			if stg in dic and dic[stg] != idx:
				return 1
			j = len(stg) - 1
			for i in range(1, j + 1):
				if isPalindrome(stg, i, j) and stg[:i] in dic:
					return 1
			for idx in range(j - 1, -1, -1):
				if isPalindrome(stg, 0, idx) and stg[idx + 1:] in dic:
					return 1
		return 0


class StringTrie:

	class Node:

		def __init__(self):
			self.parent = None
			self.childmap = {}
			self.terminal = None
			self.tcount = 0

		def terminal_iter(self):
			if self.terminal:
				yield self.terminal
			for (c, child) in sorted(self.childmap.items()):
				for s in child.terminal_iter():
					yield s

	def __init__(self):
		self.root = StringTrie.Node()

	def add(self, s):
		node = self.root
		for c in s:
			new_node = node.childmap.get(c, None)
			if new_node is None:
				new_node = StringTrie.Node()
				node.childmap[c] = new_node
			node = new_node
		node.terminal = s
		node.tcount += 1

	def match(self, s):
		node = self.root
		length = 0
		for c in s:
			new_node = node.childmap.get(c, None)
			if new_node is None:
				break
			length += 1
			node = new_node
		return (length, node)

class Solution:

	def palindromepair(self, N, arr):
		the_trie = StringTrie()
		for s in arr:
			the_trie.add(s)
		result = 0
		for s in arr:
			srev = s[::-1]
			(length, snode) = the_trie.match(s[::-1])
			if length == len(s):
				for tstr in snode.terminal_iter():
					if tstr == s and snode.tcount < 2:
						continue
					tail = tstr[length:]
					if tail == tail[::-1]:
						return 1
			elif length > 0:
				node = snode
				while node:
					tstr = node.terminal
					if tstr:
						tail = srev[length:]
						if tail == tail[::-1]:
							return 1
					node = node.parent
					length -= 1
		return 0


class Solution:

	def palindromepair(self, N, arr):

		def is_palindrome(s):
			return s == s[::-1]
		words = {}
		for i in range(N):
			words[arr[i]] = i
		for i in range(N):
			for j in range(len(arr[i]) + 1):
				(prefix, suffix) = (arr[i][:j], arr[i][j:])
				if is_palindrome(prefix):
					if suffix[::-1] in words and words[suffix[::-1]] != i:
						return 1
				if is_palindrome(suffix):
					if prefix[::-1] in words and words[prefix[::-1]] != i:
						return 1
		return 0


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end = False
		self.ind = -1

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key, ind):
		curr = self.root
		for i in key:
			if i not in curr.children:
				curr.children[i] = TrieNode()
			curr = curr.children[i]
		curr.end = True
		curr.ind = ind

	def hey(self, curr, pre, cond):
		if not curr:
			return False
		if curr.end and (not cond):
			if pre == pre[::-1] and (not cond):
				return True
		for i in curr.children:
			if self.hey(curr.children[i], pre + i, False):
				return True
		return False

	def search(self, key, index):
		curr = self.root
		for (ind, i) in enumerate(key):
			if curr.end:
				temp = key[ind:]
				if temp == temp[::-1] and curr.ind != index:
					return True
			if i not in curr.children:
				return False
			curr = curr.children[i]
		cond = False
		if curr.end:
			if curr.ind == index:
				cond = True
		return self.hey(curr, '', cond)

class Solution:

	def palindromepair(self, N, arr):
		if N == 1:
			return 0
		tree = Trie()
		ans = 0
		for (ind, i) in enumerate(arr):
			tree.insert(i[::-1], ind)
		for (ind, i) in enumerate(arr):
			if tree.search(i, ind):
				return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		hashmap_reverse = {word[::-1]: index for (index, word) in enumerate(arr)}
		ans = []
		for (index, word) in enumerate(arr):
			for i in range(len(word)):
				(left, right) = (word[:i + 1], word[i + 1:])
				if not len(left) == 0 and left == left[::-1] and (right in hashmap_reverse) and (hashmap_reverse[right] != index):
					ans.append([hashmap_reverse[right], index])
				if right == right[::-1] and left in hashmap_reverse and (hashmap_reverse[left] != index):
					ans.append([index, hashmap_reverse[left]])
		if len(ans) > 0:
			return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		sol = set()
		ind = {word: i for (i, word) in enumerate(arr)}
		for (i, word) in enumerate(arr):
			for j in range(len(word) + 1):
				left = word[:j]
				right = word[j:]
				if left == left[::-1]:
					if right[::-1] in ind and ind[right[::-1]] != i:
						sol.add((ind[right[::-1]], i))
					if len(sol) > 0:
						return 1
				if right == right[::-1]:
					if left[::-1] in ind and ind[left[::-1]] != i:
						sol.add((i, ind[left[::-1]]))
					if len(sol) > 0:
						return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		if N <= 1:
			return 0
		d = {}
		for i in range(N):
			d[arr[i][::-1]] = i
		for i in range(N):
			x = arr[i]
			for j in range(len(x) + 1):
				pre = x[:j]
				suf = x[j:]
				if pre == pre[::-1]:
					if suf in d:
						if d[suf] != i:
							return 1
				if suf == suf[::-1]:
					if pre in d:
						if d[pre] != i:
							return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		ans = []
		hash_arr = {word[::-1]: index for (index, word) in enumerate(arr)}
		for (index_i, str1) in enumerate(arr):
			for i in range(len(str1)):
				(left_str, right_str) = (str1[:i + 1], str1[i + 1:])
				if not len(left_str) == 0 and left_str == left_str[::-1] and (right_str in hash_arr) and (hash_arr[right_str] != index_i):
					ans.append([hash_arr[right_str], index_i])
				if right_str == right_str[::-1] and left_str in hash_arr and (hash_arr[left_str] != index_i):
					ans.append([index_i, hash_arr[left_str]])
		if len(ans) > 0:
			return 1
		return 0


def palindrome(S, l, r):
	while l < r:
		if S[l] != S[r]:
			return 0
		l += 1
		r -= 1
	return 1

class TrieNode:

	def __init__(self):
		self.chars = [None] * 26
		self.idx = -1
		self.indices = []

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, s, ix):
		curr = self.root
		for i in range(len(s) - 1, -1, -1):
			if palindrome(s, 0, i):
				curr.indices.append(ix)
			o = ord(s[i]) - ord('a')
			if curr.chars[o] is None:
				curr.chars[o] = TrieNode()
			curr = curr.chars[o]
		curr.idx = ix
		curr.indices.append(ix)

	def search(self, s, ix):
		curr = self.root
		n = len(s)
		for i in range(n):
			if curr.idx >= 0 and curr.idx != ix and palindrome(s, i, n - 1):
				return 1
			o = ord(s[i]) - ord('a')
			if curr.chars[o] is None:
				return 0
			curr = curr.chars[o]
		if curr:
			for idx in curr.indices:
				if ix != idx:
					return 1
		return 0

class Solution:

	def palindromepair(self, N, A):
		ans = 0
		trie = Trie()
		for i in range(N):
			trie.insert(A[i], i)
		for i in range(N):
			ans |= trie.search(A[i], i)
		return ans


class Solution:

	def ispal(self, word, i, j):
		j -= 1
		while i < j:
			if word[i] != word[j]:
				return False
			i += 1
			j -= 1
		return True

	def palindromepair(self, N, arr):
		mp = dict()
		for i in range(N):
			mp[arr[i][::-1]] = i
		for i in range(N):
			if arr[i] in mp and i != mp[arr[i]]:
				return 1
		for word in arr:
			n = len(word)
			for j in range(1, n):
				if self.ispal(word, 0, j) and word[j:] in mp:
					return 1
				if self.ispal(word, n - j, n) and word[:n - j] in mp:
					return 1
		return 0


class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.endOfWord = False
		self.ind = set()

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def isPalindrome(self, key):
		n = len(key)
		for i in range(n // 2):
			if key[i] != key[n - 1 - i]:
				return 0
		return 1

	def insert(self, key, ind):
		curr = self.root
		n = len(key)
		for i in range(n):
			ele = key[i]
			if not curr.links[ord(ele) - ord('a')]:
				curr.links[ord(ele) - ord('a')] = TrieNode()
			curr = curr.links[ord(ele) - ord('a')]
		curr.endOfWord = True
		curr.ind.add(ind)

	def search(self, key, ind):
		ll = len(key)
		curr = self.root
		for j in range(ll - 1, -1, -1):
			if not curr.links[ord(key[j]) - ord('a')]:
				return False
			curr = curr.links[ord(key[j]) - ord('a')]
			if curr.endOfWord and (ind not in curr.ind or len(curr.ind) > 1) and self.isPalindrome(key[:j]):
				return True
		return False

class Solution:

	def palindromepair(self, N, arr):
		if N == 1:
			return 0
		t = Trie()
		for i in range(N):
			t.insert(arr[i], i)
		for i in range(N):
			if t.search(arr[i], i):
				return 1
		s = Trie()
		for i in range(N):
			s.insert(arr[i][::-1], i)
		for i in range(N):
			if s.search(arr[i][::-1], i):
				return 1
		return 0


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, root, word):

		def util(root, index, word):
			if len(word) == index:
				root.isEndOfWord = True
				return
			char = word[index]
			temp = ord(char) - ord('a')
			if root.children[temp] != None:
				son = root.children[temp]
			else:
				root.children[temp] = TrieNode()
				son = root.children[temp]
			util(son, index + 1, word)
		util(root, 0, word)

class Solution:

	def palindromepair(self, N, arr):

		def check(root, st):
			i = 0
			m = len(st)
			while i < m and root != None:
				char = st[i]
				flag = False
				for k in range(26):
					if root.children[k] != None:
						flag = True
				root = root.children[ord(char) - ord('a')]
				if root == None and flag == True:
					return False
				i += 1
			if i < m:
				temp = st[i - 1:]
			elif root == None and i == m:
				temp = st[i:]
			elif root != None:
				temp = ''
				while root != None:
					flag = False
					for k in range(26):
						if root.children[k] != None:
							flag = True
							temp += chr(ord('a') + k)
							root = root.children[k]
							break
					if flag == False:
						break
			if len(temp) != 0:
				for k in range(0, len(temp) // 2):
					if temp[k] != temp[len(temp) - k - 1]:
						return False
			return True
		if N <= 1:
			return 0
		d = {}
		for i in range(N):
			d[arr[i][::-1]] = i
		for i in range(N):
			x = arr[i]
			for j in range(len(x) + 1):
				pre = x[:j]
				suf = x[j:]
				if pre == pre[::-1]:
					if suf in d:
						if d[suf] != i:
							return 1
				if suf == suf[::-1]:
					if pre in d:
						if d[pre] != i:
							return 1
		return 0


class Solution:

	def ispalindrome(self, s, n):
		i = 0
		j = n - 1
		while i <= j:
			if s[i] != s[j]:
				return False
			i += 1
			j -= 1
		return True

	def palindromepair(self, N, arr):
		m = {}
		for i in range(N):
			m[arr[i][::-1]] = i
		for i in range(N):
			n = len(arr[i])
			for j in range(n):
				d = arr[i][:j]
				e = arr[i][j:]
				if e in m and self.ispalindrome(d, j) and (m[e] != i):
					return 1
				if d in m and self.ispalindrome(e, n - j) and (m[d] != i):
					return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		d = []
		for i in arr:
			if i[::-1] in d:
				return 1
			d.append(i)
		st1 = set(arr)
		st2 = set()
		for i in st1:
			st2.add(i[::-1])
		for s in st1:
			n = len(s)
			for i in range(1, n):
				if s[:i] == s[:i][::-1] and s[i:] in st2:
					return 1
				if s[n - i:] == s[n - i:][::-1] and s[:n - i] in st2:
					return 1
		return 0


class Solution:

	def palindromepair(self, n, arr):
		if n == 1:
			return 0
		d = {}
		for i in range(n):
			d[arr[i]] = i
		for i in range(n):
			x = arr[i][::-1]
			if x in d and d[x] != i:
				return 1
		for i in range(n):
			l = len(arr[i])
			for j in range(l - 1):
				left = arr[i][0:j + 1]
				right = arr[i][j + 1:len(arr[i])]
				if left == left[::-1] and right[::-1] in d:
					return 1
				if right == right[::-1] and left[::-1] in d:
					return 1
		return 0


class Node:

	def __init__(self):
		self.links = [None for _ in range(26)]
		self.flag = False

	def is_present(self, ch):
		return self.links[ord(ch) - ord('a')] is not None

	def insert(self, ch):
		self.links[ord(ch) - ord('a')] = Node()

	def next(self, ch):
		return self.links[ord(ch) - ord('a')]

	def set_end(self):
		self.flag = True

	def end(self):
		return self.flag

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, word: str) -> None:
		node = self.root
		for v in word:
			if not node.is_present(v):
				node.insert(v)
			node = node.next(v)
		node.set_end()

	def search(self, word: str) -> bool:
		node = self.root
		for v in word:
			if not node.is_present(v):
				return False
			node = node.next(v)
		return node.end()

class Solution:

	def palindromepair(self, N, arr):
		if N == 1:
			return 0
		if len(set(arr)) != N:
			return 1
		trie = Trie()
		for v in arr:
			trie.insert(v)
		for word in arr:
			s = ''
			for i in range(len(word)):
				s += word[i]
				new_word = word + s[::-1]
				if new_word == new_word[::-1] and trie.search(s[::-1]) and (s[::-1] != word):
					return 1
			s = ''
			for i in range(len(word) - 1, -1, -1):
				s += word[i]
				new_word = s + word
				if new_word == new_word[::-1] and trie.search(s) and (s != word):
					return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		ans = []
		hs = {wrd[::-1]: i for (i, wrd) in enumerate(arr)}
		for (idx, word) in enumerate(arr):
			for i in range(len(word)):
				(left, right) = (word[0:i + 1], word[i + 1:])
				if not len(left) == 0 and left == left[::-1] and (right in hs) and (hs[right] != idx):
					ans.append([hs[right], idx])
				if right == right[::-1] and left in hs and (hs[left] != idx):
					ans.append([hs[left], idx])
		if len(ans) > 0:
			return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		index_dict = {word: i for (i, word) in enumerate(arr)}
		for (i, word) in enumerate(arr):
			for j in range(len(word) + 1):
				left_side = word[:j]
				right_side = word[j:]
				if left_side == left_side[::-1]:
					if right_side[::-1] in index_dict and index_dict[right_side[::-1]] != i:
						return 1
				if right_side == right_side[::-1]:
					if left_side[::-1] in index_dict and index_dict[left_side[::-1]] != i:
						return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		d = {}
		for (i, j) in enumerate(arr):
			d[j[::-1]] = i
		for (i, j) in enumerate(arr):
			for k in range(len(j)):
				left = j[:k + 1]
				right = j[k + 1:]
				if left == left[::-1] and right in d and (d[right] != i):
					return 1
				if right == right[::-1] and left in d and (d[left] != i):
					return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		index_dict = {word: i for (i, word) in enumerate(arr)}
		for (i, word) in enumerate(arr):
			for j in range(len(word) + 1):
				left_side = word[:j]
				right_side = word[j:]
				if left_side == left_side[::-1]:
					if right_side[::-1] in index_dict and index_dict[right_side[::-1]] != i:
						return 1
				if right_side == right_side[::-1]:
					if left_side[::-1] in index_dict and index_dict[left_side[::-1]] != i:
						return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = []
		for i in range(N):
			s = input()
			arr.append(s)
		ob = Solution()
		print(ob.palindromepair(N, arr))


class Solution:

	def palindromepair(self, N, arr):
		ans = set()
		index = {word: i for (i, word) in enumerate(arr)}
		for (i, word) in enumerate(arr):
			for j in range(len(word) + 1):
				left = word[:j]
				right = word[j:]
				if left == left[::-1]:
					if right[::-1] in index and index[right[::-1]] != i:
						ans.add((index[right[::-1]], i))
					if len(ans) > 0:
						return 1
				if right == right[::-1]:
					if left[::-1] in index and index[left[::-1]] != i:
						ans.add((i, index[left[::-1]]))
					if len(ans) > 0:
						return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = []
		for i in range(N):
			s = input()
			arr.append(s)
		ob = Solution()
		print(ob.palindromepair(N, arr))


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.eos = 0

def insert(root, key):
	curr = root
	for char in key:
		index = ord(char) - 97
		if not curr.children[index]:
			newNode = TrieNode()
			curr.children[index] = newNode
		curr = curr.children[index]
	curr.eos += 1

def search(root, key):
	curr = root
	for char in key:
		index = ord(char) - 97
		if not curr.children[index]:
			return 0
		curr = curr.children[index]
	return curr.eos

class Solution:

	def palindromepair(self, N, words):
		t = TrieNode()
		for word in words:
			insert(t, word)
		for word in words:
			for i in range(len(word)):
				rightHalf = word[:i + 1][::-1]
				newW = word + rightHalf
				if rightHalf == word:
					if search(t, rightHalf) >= 2:
						return 1
				elif newW == newW[::-1]:
					if search(t, rightHalf):
						return 1
			wordRev = word[::-1]
			for i in range(len(word)):
				leftHalf = wordRev[:i + 1]
				newW = leftHalf + word
				if leftHalf == word:
					if search(t, word) >= 2:
						return 1
				elif newW == newW[::-1]:
					if search(t, leftHalf):
						return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = []
		for i in range(N):
			s = input()
			arr.append(s)
		ob = Solution()
		print(ob.palindromepair(N, arr))


class Solution:

	def palindromepair(self, N, arr):
		d = {}
		for i in range(N):
			if arr[i] in d:
				if arr[i] == arr[i][::-1]:
					return 1
			d[arr[i]] = i

		def isPalindrome(string):
			n = len(string)
			if n == 1 or n == 0:
				return True
			(l, h) = (0, n - 1)
			while l <= h:
				if string[l] != string[h]:
					return False
				l += 1
				h -= 1
			return True
		for word in arr:
			for i in range(len(word)):
				left = word[0:i]
				right = word[i:]
				if isPalindrome(left):
					temp = right[::-1]
					if temp in d and d[word] != d[temp]:
						return 1
				if isPalindrome(right):
					temp = left[::-1]
					if left[::-1] in d and d[word] != d[temp]:
						return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = []
		for i in range(N):
			s = input()
			arr.append(s)
		ob = Solution()
		print(ob.palindromepair(N, arr))


class Solution:

	def palindromepair(self, N, arr):
		rev_hashMap = {w[::-1]: i for (i, w) in enumerate(arr)}
		for (ind, w) in enumerate(arr):
			for i in range(len(w)):
				(l, r) = (w[:i + 1], w[i + 1:])
				if l == l[::-1] and r in rev_hashMap and (rev_hashMap[r] != ind):
					return 1
				if r == r[::-1] and l in rev_hashMap and (rev_hashMap[l] != ind):
					return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = []
		for i in range(N):
			s = input()
			arr.append(s)
		ob = Solution()
		print(ob.palindromepair(N, arr))


class Solution:

	def palindromepair(self, N, arr):
		reverse = {arr[i][::-1]: i for i in range(len(arr))}
		for i in range(0, N):
			for j in range(len(arr[i])):
				(left, right) = (arr[i][0:j + 1], arr[i][j + 1:])
				if left == left[::-1] and right in reverse and (reverse[right] != i):
					return 1
				if right == right[::-1] and left in reverse and (reverse[left] != i):
					return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = []
		for i in range(N):
			s = input()
			arr.append(s)
		ob = Solution()
		print(ob.palindromepair(N, arr))


class Solution:

	def palindromepair(self, N, arr):
		reverse = {arr[i][::-1]: i for i in range(len(arr))}
		for i in range(0, N):
			for j in range(len(arr[i])):
				(left, right) = (arr[i][0:j + 1], arr[i][j + 1:])
				if left == left[::-1] and right in reverse and (reverse[right] != i):
					return 1
				if right == right[::-1] and left in reverse and (reverse[left] != i):
					return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		hashmap = {}
		for (i, val) in enumerate(arr):
			hashmap[val] = i
		for (i, word) in enumerate(arr):
			for j in range(len(word)):
				prefix = word[:j]
				suffix = word[j:]
				if prefix[::-1] in hashmap and hashmap[prefix[::-1]] != i and (suffix == suffix[::-1]):
					return 1
				if suffix[::-1] in hashmap and hashmap[suffix[::-1]] != i and (prefix == prefix[::-1]):
					return 1
		return 0


class Solution:

	def palindromepair(self, N, arr):
		reverse = dict()
		for (index, word) in enumerate(arr):
			reverse[word[::-1]] = index
		for (index, word) in enumerate(arr):
			for i in range(len(word)):
				(prefix, suffix) = (word[:i], word[i:])
				if suffix in reverse and self.isPalindrome(prefix) and (reverse[suffix] != index):
					return 1
				if prefix in reverse and self.isPalindrome(suffix) and (reverse[prefix] != index):
					return 1
		return 0

	def isPalindrome(self, word):
		return word == word[::-1]


class Solution:

	def ispalin(self, word):
		(p1, p2) = (0, len(word) - 1)
		while p1 < p2:
			if word[p1] != word[p2]:
				return False
			p1 += 1
			p2 -= 1
		return True

	def palindromepair(self, n, words):
		tmp = []
		ans = []
		d = {}
		for i in range(n):
			if words[i] != '' and self.ispalin(words[i]):
				tmp.append(i)
			d[words[i][::-1]] = i
		for i in range(n):
			if words[i] == '':
				for j in tmp:
					ans.append([i, j])
			for j in range(len(words[i])):
				s = words[i][:j]
				t = words[i][j:]
				if s in d and self.ispalin(t) and (d[s] != i):
					ans.append([i, d[s]])
				if t in d and self.ispalin(s) and (d[t] != i):
					ans.append([d[t], i])
		if len(ans):
			return 1
		return 0


def is_palindrome(string):
	return string == string[::-1]

class Trie:

	def __init__(self):
		self.root = {}

	def insert(self, word, index):
		curr_node = self.root
		n = len(word)
		for i in range(n - 1, -1, -1):
			char = word[i]
			if char not in curr_node:
				curr_node[char] = {}
			if is_palindrome(word[:i + 1]):
				curr_node['pal'] = True
			curr_node = curr_node[char]
		if '$' not in curr_node:
			curr_node['$'] = set()
		curr_node['$'].add(index)

	def search(self, word, index):
		curr_node = self.root
		n = len(word)
		for i in range(n):
			char = word[i]
			if '$' in curr_node and is_palindrome(word[i:]):
				return True
			if char not in curr_node:
				return False
			curr_node = curr_node[char]
		if 'pal' in curr_node:
			return True
		elif '$' not in curr_node:
			return False
		elif len(curr_node['$']) > 1:
			return True
		else:
			leaf_index = curr_node['$'].pop()
			if leaf_index != index:
				return True
			else:
				return False

class Solution:

	def is_palindrome(self, string):
		return string == string[::-1]

	def palindromepair(self, N, arr):
		if N <= 1:
			return 0
		trie = Trie()
		for i in range(N):
			trie.insert(arr[i], i)
		for i in range(N):
			if trie.search(arr[i], i):
				return 1
		return 0


class TrieNode:

	def __init__(self):
		self.links = [None] * 26
		self.id = -1
		self.pos = []
		self.isEnd = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def isPalindrome(self, s, i, n):
		while i < n:
			if s[i] != s[n]:
				return False
			i += 1
			n -= 1
		return True

	def insert(self, word, id):
		node = self.root
		for i in range(len(word) - 1, -1, -1):
			x = ord(word[i]) - ord('a')
			if not node.links[x]:
				node.links[x] = TrieNode()
			if self.isPalindrome(word, 0, i):
				node.pos.append(id)
			node = node.links[x]
		node.id = id
		node.pos.append(id)
		node.isEnd = True

	def Search(self, word, id, result):
		node = self.root
		for i in range(len(word)):
			x = ord(word[i]) - ord('a')
			if node.id >= 0 and node.id != id and self.isPalindrome(word, i, len(word) - 1):
				result.append((id, node.id))
			if not node.links[x]:
				return
			node = node.links[x]
		for i in node.pos:
			if i == id:
				continue
			result.append((id, i))

class Solution:

	def palindromepair(self, N, arr):
		TR = Trie()
		for i in range(N):
			TR.insert(arr[i], i)
		result = []
		for i in range(N):
			TR.Search(arr[i], i, result)
			if len(result) > 0:
				return 1
		return 0


from collections import defaultdict

class Solution:

	def isPalidrome(self, s):
		return s == s[::-1]

	def palindromepair(self, N, arr):
		map = {}
		for i in range(N):
			s = arr[i]
			map[s[::-1]] = i
		for i in range(N):
			s = arr[i]
			m = len(s)
			for j in range(m):
				pre = s[:j + 1]
				post = s[j + 1:]
				if self.isPalidrome(pre) and post in map and (map[post] != i):
					return 1
				if self.isPalidrome(post) and pre in map and (map[pre] != i):
					return 1
		return 0


from collections import defaultdict

def is_palin(s):
	n = len(s)
	for i in range(n // 2):
		if s[i] != s[n - 1 - i]:
			return False
	return True

def get_cands(w):
	yield w[::-1]
	N = len(w)
	for i in range(N - 1):
		if is_palin(w[:i + 1]):
			yield w[-1:i:-1]
	for i in range(N - 1, 0, -1):
		if is_palin(w[i:]):
			yield w[:i][::-1]

class Solution:

	def palindromepair(self, N, arr):
		wd = defaultdict(lambda : 0)
		for w in arr:
			wd[w] += 1
		words = set(wd.keys())
		for w in words:
			for cand in get_cands(w):
				if cand in words:
					if cand == w:
						if wd[w] > 1:
							return 1
					else:
						return 1
		return 0