Given a string S which contains only small letters. The task is to make a square matrix from string S. Then perform the following operations.
1. In each column delete the characters which occur more than one.
2. Column-wise sort the remaining characters in order abcd....wxyz. But print them in order azbycxdw....  
For example, after operation 1 if the remaining characters in a column are cedjki then after sorting they become cdeijk , now when printed in the given order the output will be ckdjei. If there's no character remaining Print 0.
Note: Length of the Input String is always a Perfect Square.
 
Example 1:
Input:
S = "adgkbdhlceilcfjm"
Output:
abefgjhikm
Explanation:
Matrix will be
a d g k
b d h l
c e i  l
c f  j m
In 1st column 'c', in 2nd column 'd' and in
4th column 'l' has occurred more than once.
So after deleting them and sorting the
remaining characters the matrix become 
   a - g  k
   b - h  -
   - e i   -
   - f  j  m 
So after operation 2 we get 'ab' from 1st
column, 'ef' from 2nd column, 'gjhi' from
3rd column and 'km' from 4th column. Appending
all of them we get the output as  "abefgjhikm".
Example 2:
Input:
S = "abcabcabc"
Output:
0
Explanation:
Matrix will be
a b c
a b c
a b c
So, There will be no letters remaining
and the output will be 0. 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function matrixGame() which takes a String S and returns the answer.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
 
Constraints
1 <= |S| <= 10^{5}

Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def matrixGame(self, S):

        # code here

Solutions:
class Solution:

	def matrixGame(self, S):
		if len(S) == 1:
			return S
		elif len(S) < 5:
			return 0
		l = len(S)
		import math
		k = int(math.sqrt(l))
		M = []
		for i in range(0, len(S), k):
			M.append(S[i:i + k])
		W = []
		for i in range(k):
			b = ''
			for j in range(k):
				b += M[j][i]
			g = ''
			for i in b:
				if b.count(i) == 1:
					g += i
			W.append(g)
		d = ''
		for i in W:
			if len(i) < 3:
				d += i
			else:
				for j in range(len(i) // 2):
					d += i[j]
					d += i[-(j + 1)]
				if len(i) % 2 == 1:
					d += i[len(i) // 2]
		if len(d) == 0:
			return 0
		return d


class Solution:

	def matrixGame(self, S):
		ans = ''
		n = int(math.sqrt(len(S)))
		mat = [['0' for i in range(n)] for j in range(n)]
		k = 0
		for i in range(n):
			for j in range(n):
				mat[i][j] = S[k]
				k += 1
		for i in range(n):
			freq = [0] * 26
			s = ''
			for j in range(n):
				freq[97 - ord(mat[j][i])] += 1
			for j in range(n):
				if freq[97 - ord(mat[j][i])] == 1:
					s += mat[j][i]
			if len(s) % 2:
				for j in range(len(s) // 2):
					ans += s[j]
					ans += s[len(s) - j - 1]
				ans += s[len(s) // 2]
			else:
				for j in range(len(s) // 2):
					ans += s[j]
					ans += s[len(s) - j - 1]
		if len(ans) == 0:
			ans = '0'
		return ans


class Solution:

	def matrixGame(self, S):
		n = len(S)
		k = int(n ** 0.5)
		t = ''
		for i in range(k):
			j = i
			s = {}
			while j < n:
				if S[j] not in s:
					s[S[j]] = 1
				else:
					s[S[j]] += 1
				j += k
			j = i
			c = []
			while j < n:
				if s[S[j]] == 1:
					c.append(S[j])
				j = j + k
			h = 0
			p = len(c) - 1
			while h <= p:
				t += c[h]
				h += 1
				if h > p:
					break
				t += c[p]
				p -= 1
		if len(t) == 0:
			return '0'
		return t


class Solution:

	def matrixGame(self, S):
		import math
		from collections import OrderedDict
		n = len(S)
		m = int(math.sqrt(n))
		i = 0
		ans = ''
		while i < m:
			j = i
			k = 0
			d = OrderedDict()
			while k < m:
				d[S[j]] = d.get(S[j], 0) + 1
				j += m
				k += 1
			arr = []
			for (x, v) in d.items():
				if v == 1:
					arr.append(x)
			t = len(arr) // 2
			for p in range(t):
				ans += arr[p]
				ans += arr[-1 * (p + 1)]
			if len(arr) % 2 != 0:
				ans += arr[t]
			d.clear()
			i += 1
		if ans:
			return ans
		return 0


class Solution:

	def matrixGame(self, S):
		ans = ''
		n = int(math.sqrt(len(S)))
		mat = [['0' for i in range(n)] for j in range(n)]
		k = 0
		for i in range(n):
			for j in range(n):
				mat[i][j] = S[k]
				k += 1
		for i in range(n):
			freq = [0] * 26
			s = ''
			for j in range(n):
				freq[97 - ord(mat[j][i])] += 1
			for j in range(n):
				if freq[97 - ord(mat[j][i])] == 1:
					s += mat[j][i]
			if len(s) % 2:
				for j in range(len(s) // 2):
					ans += s[j]
					ans += s[len(s) - j - 1]
				ans += s[len(s) // 2]
			else:
				for j in range(len(s) // 2):
					ans += s[j]
					ans += s[len(s) - j - 1]
		if len(ans) == 0:
			ans = '0'
		return ans
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.matrixGame(S))