Given an array of non-negative integers of size N. Find the maximum possible XOR between two numbers present in the array. 
Example 1:
Input:
Arr = {25, 10, 2, 8, 5, 3}
Output: 28
Explanation:
The maximum result is 5 ^ 25 = 28.
Example 2:
Input :
Arr = {1, 2, 3, 4, 5, 6, 7}
Output : 7
Explanation :
The maximum result is 1 ^ 6 = 7.
Your task :
You don't need to read input or print anything. Your task is to complete the function max_xor() which takes an array of integers and it's size as input and returns maximum XOR of two numbers in an array.
 
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
 
Constraints:
2 <= N <=5*10^{4}
1<= A[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def max_xor(self, arr, n):

        #code here

Solutions:
from math import log

class Solution:

	def max_xor(self, arr, n):
		try:
			l = int(log(max(arr), 2))
		except:
			l = 1
		(mask, res) = (0, 0)
		for i in range(l, -1, -1):
			mask |= 1 << i
			S = set((mask & num for num in arr))
			temp = res | 1 << i
			for num in S:
				if num ^ temp in S:
					res = temp
					break
		return res


class Trie:

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

	def put(self, num):
		node = self.root
		for i in range(30, -1, -1):
			bit = num >> i & 1
			if not bit in node:
				node[bit] = {}
			node = node[bit]

	def get(self, num):
		node = self.root
		ans = 0
		for i in range(30, -1, -1):
			bit = num >> i & 1
			op_bit = 1 - bit
			if op_bit in node:
				node = node[op_bit]
				ans |= 1 << i
			else:
				node = node[bit]
		return ans

class Solution:

	def max_xor(self, arr, n):
		t = Trie()
		t.put(arr[0])
		ans = 0
		for i in range(1, len(arr)):
			ans = max(ans, t.get(arr[i]))
			t.put(arr[i])
		return ans


import math

class Solution:

	def max_xor(self, arr, n):

		def insert(root, word):
			for c in word:
				if c not in root:
					root[c] = {}
				root = root[c]

		def findMaxXOR(root, bin_str):
			bin_ans = ''
			for c in bin_str:
				bit = str(1 ^ int(c))
				if bit in root:
					bin_ans += bit
					root = root[bit]
				else:
					bin_ans += c
					root = root[c]
			return int(bin_ans, 2) ^ int(bin_str, 2)
		root = {}
		max_xor = -1
		max_num = max(arr)
		k = math.floor(math.log(max_num, 2)) + 1 if max_num != 0 else 1
		for num in arr:
			bin_str = bin(num)[2:]
			bin_str = bin_str.zfill(k)
			insert(root, bin_str)
		for num in arr:
			bin_str = bin(num)[2:]
			bin_str = bin_str.zfill(k)
			max_xor = max(findMaxXOR(root, bin_str), max_xor)
		return max_xor


class TrieNode:

	def __init__(self):
		self.child = [0] * 2

class Trie:

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

	def insert(self, num):
		curNode = self.root
		for i in range(31, -1, -1):
			setBit = 0
			if 1 << i & num:
				setBit = 1
			if curNode.child[setBit] == 0:
				curNode.child[setBit] = TrieNode()
			curNode = curNode.child[setBit]

	def maxXor(self, arr, n):
		ans = 0
		for num in arr:
			maxi = 0
			curNode = self.root
			for i in range(31, -1, -1):
				bit = 1
				if 1 << i & num:
					bit = 0
				if curNode.child[bit] == 0:
					curNode = curNode.child[bit ^ 1]
					maxi |= (bit ^ 1) << i
				else:
					curNode = curNode.child[bit]
					maxi |= bit << i
			ans = max(ans, num ^ maxi)
		return ans

class Solution:

	def max_xor(self, arr, n):
		trie = Trie()
		for num in arr:
			trie.insert(num)
		return trie.maxXor(arr, n)


import math

class Solution:

	def max_xor(self, arr, n):
		if max(arr) == 0:
			return 0
		l = int(math.log2(max(arr))) + 1
		ans = 0
		for i in range(l - 1, -1, -1):
			ans = ans << 1
			p = set()
			for x in arr:
				p.add(x >> i)
			flag = False
			for x in p:
				if ans ^ 1 ^ x in p:
					flag = True
			if not flag:
				ans += 0
			else:
				ans += 1
		return ans


class TrieNode:

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

class Solution:

	def Insert_Into_Trie(self, binary_str, root):
		for bit in binary_str:
			if bit in root.bin_dict:
				root = root.bin_dict[bit]
			else:
				root.bin_dict[bit] = TrieNode()
				root = root.bin_dict[bit]

	def Get_Binary_Str(self, no):
		binary_str = bin(no)[2:]
		return '0' * (32 - len(binary_str)) + binary_str

	def Construct_Trie(self, arr):
		(root, ans, n) = (TrieNode(), 0, len(arr))
		(binary_str, temp_root) = (self.Get_Binary_Str(arr[0]), root)
		for bit in binary_str:
			temp_root.bin_dict[bit] = TrieNode()
			temp_root = temp_root.bin_dict[bit]
		for i in range(1, n):
			(temp_root, bin_str, bin_form) = (root, '', self.Get_Binary_Str(arr[i]))
			for bit in bin_form:
				opp_bit = '1' if bit == '0' else '0'
				if opp_bit in temp_root.bin_dict:
					bin_str += '1'
					temp_root = temp_root.bin_dict[opp_bit]
				else:
					bin_str += '0'
					temp_root = temp_root.bin_dict[bit]
			ans = max(ans, int(bin_str, 2))
			self.Insert_Into_Trie(bin_form, root)
		return ans

	def max_xor(self, arr, n):
		return self.Construct_Trie(arr)


class Solution:

	def max_xor(self, arr, n):
		maxx = 0
		mask = 0
		se = set()
		for i in range(30, -1, -1):
			mask |= 1 << i
			newMaxx = maxx | 1 << i
			for i in range(n):
				se.add(arr[i] & mask)
			for prefix in se:
				if newMaxx ^ prefix in se:
					maxx = newMaxx
					break
			se.clear()
		return maxx


class TrieNode:

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

	def increase(self, number):
		cur = self
		for i in range(31, -1, -1):
			bit = number >> i & 1
			if bit not in cur.child:
				cur.child[bit] = TrieNode()
			cur = cur.child[bit]

	def findMax(self, number):
		(cur, ans) = (self, 0)
		for i in range(31, -1, -1):
			bit = number >> i & 1
			if 1 - bit in cur.child:
				cur = cur.child[1 - bit]
				ans |= 1 << i
			else:
				cur = cur.child[bit]
		return ans

class Solution:

	def max_xor(self, nums, n):
		trieNode = TrieNode()
		for x in nums:
			trieNode.increase(x)
		ans = 0
		for x in nums:
			ans = max(ans, trieNode.findMax(x))
		return ans


class Node:

	def __init__(self):
		self.children = dict()

	def get(self, node):
		return self.children[node]

	def contains_key(self, key):
		return key in self.children

	def put(self, key):
		self.children[key] = Node()

class Trie:

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

	def insert(self, num):
		node = self.root
		for i in reversed(range(32)):
			bit = num >> i & 1
			if not node.contains_key(bit):
				node.put(bit)
			node = node.get(bit)

	def get_max_xor(self, num):
		node = self.root
		max_num = 0
		for i in reversed(range(32)):
			bit = num >> i & 1
			if node.contains_key(1 - bit):
				max_num += 2 ** i
				node = node.get(1 - bit)
			else:
				node = node.get(bit)
		return max_num

class Solution:

	def max_xor(self, nums, n):
		trie = Trie()
		max_xor = 0
		for num in nums:
			trie.insert(num)
		for num in nums:
			max_xor = max(max_xor, trie.get_max_xor(num))
		return max_xor


class TrieNode:

	def __init__(self):
		self.children = [None] * 2

def insert(root, num):
	curr = root
	for i in range(31, -1, -1):
		bit = num >> i & 1
		if curr.children[bit] is None:
			curr.children[bit] = TrieNode()
		curr = curr.children[bit]

class Solution:

	def max_xor(self, arr, n):
		root = TrieNode()
		for num in arr:
			insert(root, num)
		max_xor = 0
		for num in arr:
			curr = root
			xor = 0
			for i in range(31, -1, -1):
				bit = num >> i & 1
				if curr.children[bit ^ 1] is not None:
					xor |= 1 << i
					curr = curr.children[bit ^ 1]
				else:
					curr = curr.children[bit]
			max_xor = max(max_xor, xor)
		return max_xor


class TrieNode:

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

class Trie:

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

	def insert(self, n):
		temp = self.root
		i = 31
		while i >= 0:
			bit = n >> i & 1
			if bit not in temp.children:
				temp.children[bit] = TrieNode()
			temp = temp.children[bit]
			i -= 1

	def max_xor_helper(self, value):
		temp = self.root
		current_ans = 0
		i = 31
		while i >= 0:
			bit = value >> i & 1
			if bit ^ 1 in temp.children:
				temp = temp.children[bit ^ 1]
				current_ans += 1 << i
			else:
				temp = temp.children[bit]
			i -= 1
		return current_ans

class Solution:

	def max_xor(self, arr, n):
		trie = Trie()
		max_val = 0
		trie.insert(arr[0])
		for num in arr[1:]:
			max_val = max(trie.max_xor_helper(num), max_val)
			trie.insert(num)
		return max_val


class node:

	def __init__(self, val=None):
		self.val = val
		self.one = None
		self.zero = None

class Solution:

	def __init__(self):
		self.root = node(None)

	def insert(self, x):
		temp = self.root
		for i in range(31, -1, -1):
			bit = 1 << i & x
			if bit:
				if not temp.one:
					temp.one = node()
				temp = temp.one
			else:
				if not temp.zero:
					temp.zero = node()
				temp = temp.zero
		temp.val = x

	def show(self, root):
		if not root:
			return
		if root.val != None:
			print(root.val)
			return
		self.show(root.zero)
		self.show(root.one)

	def max_xor_check(self, x):
		temp = self.root
		for i in range(31, -1, -1):
			bit = 1 << i & x
			if bit:
				if temp.zero:
					temp = temp.zero
				else:
					temp = temp.one
			elif temp.one:
				temp = temp.one
			else:
				temp = temp.zero
		return temp.val ^ x

	def max_xor(self, arr, n):
		temp = self.root
		self.insert(arr[0])
		m_xor = 0
		for x in arr[1:]:
			m_xor = max(m_xor, self.max_xor_check(x))
			self.insert(x)
		return m_xor


class Node:

	def __init__(self, val=None):
		self.val = val
		self.child = [None, None]

class Trie:

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

	def insert(self, s):

		def solve(head, s):
			if len(s) == 0:
				return
			if head.child[int(s[0])] != None:
				child = head.child[int(s[0])]
			else:
				child = Node(int(s[0]))
				head.child[int(s[0])] = child
			solve(child, s[1:])
		solve(self.head, s)

	def find(self, s):
		ans = []

		def solve2(head, s):
			if len(s) == 0:
				return
			if head.child[1 - int(s[0])] is not None:
				ans.append('1')
				child = head.child[1 - int(s[0])]
			else:
				ans.append('0')
				child = head.child[int(s[0])]
			solve2(child, s[1:])
		solve2(self.head, s)
		return int(''.join(ans), 2)

class Solution:

	def max_xor(self, arr, n):
		t = Trie()
		fill = len(bin(max(arr)))
		for i in arr:
			tmp = bin(i)[2:]
			tmp = tmp.zfill(fill)
			t.insert(tmp)

		def solve3(arr, x, t):
			x = bin(x)[2:]
			x = x.zfill(fill)
			ans = t.find(x)
			return ans
		ans = 0
		for i in arr:
			tmp = solve3(arr, i, t)
			ans = max(ans, tmp)
		return ans


class Node:

	def __init__(self):
		self.zero = None
		self.one = None

class Trie:

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

	def insert(self, val):
		tem = self.root
		for i in range(31, -1, -1):
			bit = val >> i & 1
			if bit == 0:
				if tem.zero == None:
					tem.zero = Node()
				tem = tem.zero
			else:
				if tem.one == None:
					tem.one = Node()
				tem = tem.one

	def max_xor_fin(self, val):
		tem = self.root
		ans = 0
		for i in range(31, -1, -1):
			bit = val >> i & 1
			if bit == 0:
				if tem.one:
					tem = tem.one
					ans += 1 << i
				else:
					tem = tem.zero
			elif tem.zero:
				tem = tem.zero
				ans += 1 << i
			else:
				tem = tem.one
		return ans

	def max_xor(self, arr, n):
		maxi = 0
		self.insert(arr[0])
		for i in range(1, n):
			maxi = max(self.max_xor_fin(arr[i]), maxi)
			self.insert(arr[i])
		return maxi

class Solution:

	def max_xor(self, arr, n):
		tri = Trie()
		return tri.max_xor(arr, n)


SIZE = 19

class TrieNode:

	def __init__(self):
		self.children = [None] * 2

class Trie:

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

	def insert(self, N):
		curr = self.root
		for i in range(SIZE, -1, -1):
			bit = N >> i & 1
			if curr.children[bit] is None:
				curr.children[bit] = TrieNode()
			curr = curr.children[bit]

	def search(self, N):
		curr = self.root
		ret = 0
		for i in range(SIZE, -1, -1):
			bit = N >> i & 1
			if curr.children[bit]:
				if curr.children[bit ^ 1]:
					curr = curr.children[bit ^ 1]
					ret += 1 << i
				else:
					curr = curr.children[bit]
			else:
				curr = curr.children[bit ^ 1]
				ret += 1 << i
		return ret

class Solution:

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


class Solution:

	def max_xor(self, nums, n):
		nums.sort(reverse=True)
		m = len(str(bin(max(nums)))) - 2
		dup_m = m
		res = 0
		bit = 1 << m - 1
		for i in range(0, m):
			(dup_m, dic, temp) = (dup_m - 1, {}, [])
			temp = []
			for i in range(0, n):
				if nums[i] & bit in dic:
					dic[nums[i] & bit] += 1
				else:
					dic[nums[i] & bit] = 1
					temp.append(nums[i] & bit)
			k = len(temp)
			for i in range(0, k):
				if bit ^ temp[i] in dic:
					if bit ^ temp[i] == temp[i] and dic[bit ^ temp[i]] < 2:
						continue
					res = bit
					break
			else:
				bit ^= 1 << dup_m
			if dup_m - 1 >= 0:
				bit ^= 1 << dup_m - 1
		return res


class Solution:

	def max_xor(self, arr, n):
		prefix_mask = 0
		ans = 0
		for i in range(31, -1, -1):
			prefix_mask |= 1 << i
			prefixes = set([prefix_mask & num for num in arr])
			newMax = ans | 1 << i
			for pre in prefixes:
				if pre ^ newMax in prefixes:
					ans = newMax
					break
		return ans


class node:

	def __init__(self, data):
		self.data = data
		self.childs = {}

class trie:

	def __init__(self):
		self.head = node(0)
		self.array = []

	def insert(self, num):
		curr = self.head
		inbit = ''
		for i in range(32, -1, -1):
			if num & 1 << i:
				inbit += '1'
				if '1' in curr.childs:
					curr = curr.childs['1']
				else:
					curr.childs['1'] = node('1')
					curr = curr.childs['1']
			else:
				inbit += '0'
				if '0' in curr.childs:
					curr = curr.childs['0']
				else:
					curr.childs['0'] = node('0')
					curr = curr.childs['0']
		curr.childs['#'] = num
		self.array.append(inbit)

	def getmax(self, i):
		inbit = self.array[i]
		start = 0
		curr = self.head
		while start < len(inbit):
			if inbit[start] == '1':
				currbit = '0'
			else:
				currbit = '1'
			if currbit in curr.childs:
				curr = curr.childs[currbit]
			else:
				curr = curr.childs[inbit[start]]
			start += 1
		return curr.childs['#']

class Solution:

	def max_xor(self, arr, n):
		if n == 1:
			return 0
		else:
			t = trie()
			for i in arr:
				t.insert(i)
			maxi = 0
			for i in range(len(arr)):
				curr = t.getmax(i)
				maxi = max(maxi, curr ^ arr[i])
		return maxi


class TrieNode:

	def __init__(self):
		self.zero = None
		self.one = None

class Solution:

	def max_xor(self, arr, n):
		max_res = float('-inf')
		root = TrieNode()
		for ele in arr:
			self.insertNode(ele, root)
		for ele in arr:
			max_res = max(max_res, self.findMax(ele, root))
		return max_res

	def insertNode(self, data, root):
		i = 31
		while i >= 0:
			if data >> i & 1:
				if not root.one:
					root.one = TrieNode()
				root = root.one
			else:
				if not root.zero:
					root.zero = TrieNode()
				root = root.zero
			i -= 1

	def findMax(self, data, root):
		res = 0
		i = 31
		while i >= 0:
			if data >> i & 1:
				if root.zero:
					res |= 1 << i
					root = root.zero
				else:
					root = root.one
			elif root.one:
				res |= 1 << i
				root = root.one
			else:
				root = root.zero
			i -= 1
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.max_xor(arr, n))


class Solution:

	def max_xor(self, arr, n):
		ans = 0
		mask = 0
		for i in range(31, -1, -1):
			mask |= 1 << i
			temp = ans | 1 << i
			s = set()
			for j in arr:
				num = j & mask
				if num ^ temp in s:
					ans = temp
					break
				s.add(num)
			s.clear()
		return ans


class Solution:

	def max_xor(self, arr, n):
		maxx = 0
		mask = 0
		se = set()
		for i in range(30, -1, -1):
			mask |= 1 << i
			new = maxx | 1 << i
			for j in range(n):
				se.add(arr[j] & mask)
			for pre in se:
				if new ^ pre in se:
					maxx = new
					break
			se.clear()
		return maxx


class Solution:

	def max_xor(self, arr, n):
		r = 0
		k = 0
		for i in range(31, -1, -1):
			m = r | 1 << i
			s = set()
			k = k | 1 << i
			for j in arr:
				l = j & k
				s.add(l)
			for pre in s:
				if m ^ pre in s:
					r = m
					break
		return r


from collections import defaultdict

class TrieNode:

	def __init__(self):
		self.children = defaultdict(TrieNode)
		self.val = 0

class Trie:

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

	def insert(self, binary):
		cur = self.root
		for char in binary:
			cur = cur.children[int(char)]

	def Get_Max(self, binary) -> int:
		result = 0
		cur = self.root
		for char in binary:
			opposite = 1 - int(char)
			if opposite in cur.children:
				result = result << 1 | 1
				cur = cur.children[opposite]
			else:
				result = result << 1
				cur = cur.children[int(char)]
		return result

class Solution:

	def max_xor(self, nums, n):
		trie = Trie()
		result = float('-inf')
		maxLen = len(bin(max(nums))[2:])
		for num in nums:
			key = bin(num)[2:].zfill(maxLen)
			trie.insert(key)
			result = max(result, trie.Get_Max(key))
		return result


class TrieNode:

	def __init__(self):
		self.bits = [None, None]

	def ContainsKey(self, bit):
		return self.bits[bit] != None

	def Get(self, bit):
		return self.bits[bit]

	def PutKey(self, bit, node):
		self.bits[bit] = node

class Trie:

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

	def insert(self, num):
		temp = self.node
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if not temp.ContainsKey(bit):
				temp.PutKey(bit, Trie())
			temp = temp.Get(bit).node

	def Get_Max(self, num):
		temp = self.node
		M = 0
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if not temp.ContainsKey(1 ^ bit):
				temp = temp.Get(bit).node
			else:
				M |= 1 << i
				temp = temp.Get(1 ^ bit).node
		return M

class Solution:

	def max_xor(self, arr, n):
		trie = Trie()
		for a in arr:
			trie.insert(a)
		M = 0
		for b in arr:
			M = max(M, trie.Get_Max(b))
		return M


class Node:

	def __init__(self):
		self.links = [None] * 2

	def containsKey(self, bit):
		return self.links[bit] != None

	def put(self, bit, node):
		self.links[bit] = node

	def get(self, bit):
		return self.links[bit]

class Trie:

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

	def insert(self, num):
		node = self.root
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if not node.containsKey(bit):
				node.put(bit, Node())
			node = node.get(bit)

	def getMax(self, num):
		node = self.root
		maxNum = 0
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if node.containsKey(1 - bit):
				maxNum = maxNum | 1 << i
				node = node.get(1 - bit)
			else:
				node = node.get(bit)
		return maxNum

class Solution:

	def max_xor(self, arr, n):
		trie = Trie()
		for num in arr:
			trie.insert(num)
		mx = -1
		for num in arr:
			mx = max(mx, trie.getMax(num))
		return mx


class Node:

	def __init__(self):
		self.links = [None for i in range(2)]

	def contains(self, bit):
		return self.links[bit] != None

	def put(self, bit, curr):
		self.links[bit] = curr

	def get(self, bit):
		return self.links[bit]

class Trie:

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

	def insert(self, num):
		node = self.root
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if not node.contains(bit):
				node.put(bit, Node())
			node = node.get(bit)

	def maximum(self, num):
		node = self.root
		maxi = 0
		for i in range(31, -1, -1):
			bit = num >> i & 1
			if node.contains(1 - bit):
				maxi = maxi | 1 << i
				node = node.get(1 - bit)
			else:
				node = node.get(bit)
		return maxi

class Solution:

	def max_xor(self, arr, n):
		node = Trie()
		for i in range(n):
			node.insert(arr[i])
		ans = 0
		for i in range(n):
			ans = max(ans, node.maximum(arr[i]))
		return ans


class Solution:

	def max_xor(self, nums, n):
		(m, mask) = (0, 0)
		for i in range(32)[::-1]:
			mask |= 1 << i
			prefixes = {n & mask for n in nums}
			tmp = m | 1 << i
			if any((prefix ^ tmp in prefixes for prefix in prefixes)):
				m = tmp
		return m


class node:

	def __init__(self):
		self.o = None
		self.z = None
		self.v = 0

class tri:

	def __init__(self):
		self.r = node()

	def ins(self, a):
		p = self.r
		for i in range(31, -1, -1):
			x = a & 1 << i
			if x:
				if p.o:
					p = p.o
				else:
					p.o = node()
					p = p.o
			elif p.z:
				p = p.z
			else:
				p.z = node()
				p = p.z
		p.v = a

	def iss(self, a):
		p = self.r
		for i in range(31, -1, -1):
			x = a & 1 << i
			if x == 0:
				if p.o:
					p = p.o
				else:
					p = p.z
			elif p.z:
				p = p.z
			else:
				p = p.o
		return p.v ^ a

class Solution:

	def max_xor(self, arr, n):
		t = tri()
		ans = 0
		for i in arr:
			t.ins(i)
		for i in arr:
			ans = max(ans, t.iss(i))
		return ans


class Trie:

	def __init__(self):
		self.left = None
		self.right = None

def insert(n, l):
	head = None
	for i in range(n):
		val = l[i]
		current_node = head
		for j in range(31, -1, -1):
			present_bit = val >> j & 1
			node = Trie()
			if head is None:
				head = node
				current_node = node
				node1 = Trie()
				if present_bit == 0:
					current_node.left = node1
				else:
					current_node.right = node1
				current_node = node1
			elif present_bit == 0:
				if current_node.left:
					current_node = current_node.left
				else:
					current_node.left = node
					current_node = node
			elif current_node.right:
				current_node = current_node.right
			else:
				current_node.right = node
				current_node = node
	return head

def getMaxXor(n, l, head):
	ans = 0
	for i in range(n):
		temp_ans = 0
		current_node = head
		for j in range(31, -1, -1):
			present_bit = l[i] >> j & 1
			if present_bit == 1:
				if current_node.left:
					current_node = current_node.left
					temp_ans += 2 ** j
				else:
					current_node = current_node.right
			elif current_node.right:
				current_node = current_node.right
				temp_ans += 2 ** j
			else:
				current_node = current_node.left
		if temp_ans > ans:
			ans = temp_ans
	return ans

class Solution:

	def max_xor(self, arr, n):
		head = insert(n, arr)
		return getMaxXor(n, arr, head)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
ANS = []
max_bit = 22

def solve():
	trie = [-1] * 2 ** (max_bit + 2)
	trie[1] = 0
	for i in range(n):
		x = a[i]
		b = []
		for j in range(max_bit):
			if x % 2:
				b.append(1)
			else:
				b.append(0)
			x //= 2
		b = b[::-1]
		ind = 1
		for j in range(max_bit):
			ind *= 2
			if b[j] == 1:
				ind += 1
				trie[ind] = 1
			else:
				trie[ind] = 0
	good = 2 ** 22 - 1
	pp = 2 ** 22
	ans = 0
	for i in range(n):
		x = good ^ a[i]
		b = []
		for j in range(max_bit):
			if x % 2:
				b.append(1)
			else:
				b.append(0)
			x //= 2
		b = b[::-1]
		ind = 1
		val = good
		p = pp
		for j in range(max_bit):
			ind *= 2
			p //= 2
			if b[j] == 1:
				if trie[ind + 1] != 1:
					val -= p
				else:
					ind += 1
			elif trie[ind] != 0:
				val -= p
				ind += 1
		ans = max(ans, val)
	return ans
for t in range(int(input())):
	n = int(input())
	a = ints()
	print(solve())
quit()


from sys import stdin
input = stdin.readline

class trie:

	def __init__(self):
		self.child = []
		self.data = None

	def insert(self, value):
		self.child.append(trie())
		self.child[-1].data = value

	def make(self, value):
		for x in self.child:
			if x.data == value:
				return x
		self.insert(value)
		return self.child[-1]

def dfs(root, val, lvl=0):
	ans = 0
	if len(root.child) == 1:
		value = val >> 29 - lvl & 1
		ans += dfs(root.child[0], val, lvl + 1)
		ans += (value != root.child[0].data) * (1 << 29 - lvl)
	elif len(root.child) == 2:
		value = val >> 29 - lvl & 1
		(left, right) = (root.child[0], root.child[1])
		if left.data == 1:
			(left, right) = (right, left)
		if value != left.data:
			ans += dfs(left, val, lvl + 1)
		else:
			ans += dfs(right, val, lvl + 1)
		ans += 1 << 29 - lvl
	return ans

def answer():
	head = trie()
	for i in range(n):
		root = head
		for bit in range(30 - 1, -1, -1):
			root = root.make(a[i] >> bit & 1)
	ans = 0
	for i in range(n):
		ans = max(ans, dfs(head, a[i]))
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())
exit(0)


class Solution:

	class Trie:

		class TrieNode:

			def __init__(self):
				self.links = [None for i in range(2)]

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

		def getbit(self, num, ind):
			return num >> ind & 1

		def insert(self, num, maxlen):
			node = self.root
			binary = bin(num)
			for i in range(maxlen - 1, -1, -1):
				bit = self.getbit(num, i)
				if node.links[bit] == None:
					node.links[bit] = self.TrieNode()
				node = node.links[bit]

		def getMax(self, num, maxlen):
			node = self.root
			maxnum = 0
			for i in range(maxlen - 1, -1, -1):
				bit = self.getbit(num, i)
				if node.links[1 - bit] != None:
					maxnum = maxnum | 1 << i
					node = node.links[1 - bit]
				else:
					node = node.links[bit]
			return maxnum

	def max_xor(self, A, n):
		r = self.Trie()
		maxlen = len(bin(max(A))[2:])
		ans = 0
		for i in A:
			r.insert(i, maxlen)
			ans = max(ans, r.getMax(i, maxlen))
		return ans


class Trie:

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

class Solution:

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

	def insert(self, num):
		binary = bin(num)[2:].zfill(32)
		curr = self.root
		for c in binary:
			if c not in curr.children:
				curr.children[c] = Trie()
			curr = curr.children[c]

	def findMax(self, num):
		binary = bin(num)[2:].zfill(32)
		curr = self.root
		res = ''
		for bit in binary:
			if bit == '0':
				opp_bit = '1'
			elif bit == '1':
				opp_bit = '0'
			if opp_bit in curr.children:
				res += opp_bit
				curr = curr.children[opp_bit]
			else:
				res += bit
				curr = curr.children[bit]
		return int(res, 2) ^ num

	def max_xor(self, nums, n):
		maxXor = 0
		for num in nums:
			self.insert(num)
		for num in nums:
			maxXor = max(maxXor, self.findMax(num))
		return maxXor


class Solution:

	def max_xor(self, nums, n):
		overAllMax = 0
		trie = Trie()
		for num in nums:
			trie.insert(num)
		for num in nums:
			currMax = trie.getMaxXor(num)
			overAllMax = max(overAllMax, currMax)
		return overAllMax

class Node:

	def __init__(self):
		self.links = [None, None]

	def put(self, bit):
		self.links[bit] = Node()

	def containsKey(self, bit):
		return None != self.links[bit]

	def getNext(self, bit):
		return self.links[bit]

class Trie:

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

	def insert(self, num):
		node = self.root
		for i in range(32 - 1, -1, -1):
			currBit = num >> i & 1
			if not node.containsKey(currBit):
				node.put(currBit)
			node = node.getNext(currBit)

	def getMaxXor(self, num2):
		maxXor = 0
		node = self.root
		for i in range(32 - 1, -1, -1):
			currBit = num2 >> i & 1
			desired = 1 - currBit
			if node.containsKey(desired):
				maxXor = maxXor | 1 << i
				node = node.getNext(desired)
			else:
				node = node.getNext(currBit)
		return maxXor


class Solution:

	def max_xor(self, arr, n):
		trie = self.getTrie(arr, n)
		freq = {}
		for i in arr:
			if i not in freq:
				freq[i] = 1
			else:
				freq[i] += 1
		ans = -1
		for i in range(n):
			num = arr[i]
			binNum = bin(num)[2:]
			binNum = '0' * (32 - len(binNum)) + binNum
			current = trie
			fn = ''
			for value in binNum:
				v = '1' if value == '0' else '0'
				if v in current:
					fn += v
					current = current[v]
				else:
					fn += value
					current = current[value]
			fn = int(fn, 2)
			ans = max(ans, fn ^ num)
		return ans

	def getTrie(self, arr, n):
		trie = {}
		for i in range(n):
			currentNumber = arr[i]
			binNum = bin(currentNumber)[2:]
			binNum = '0' * (32 - len(binNum)) + binNum
			current = trie
			for value in binNum:
				if value not in current:
					current[value] = {}
				current = current[value]
		return trie


from collections import defaultdict

class Node:

	def __init__(self):
		self.children = dict()
		self.val = 0

class Trie:

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

	def add_nums(self, num):
		node = self.root
		for shift in range(self.n, -1, -1):
			val = 1 if num & 1 << shift else 0
			if val not in node.children:
				node.children[val] = Node()
			node = node.children[val]
		node.val = num

class Solution:

	def max_xor(self, arr, n):
		size = len(bin(max(arr))) - 2
		trie = Trie(size)
		for i in arr:
			trie.add_nums(i)
		ans = 0
		for i in arr:
			node = trie.root
			for j in range(size, -1, -1):
				val = 1 if i & 1 << j else 0
				node = node.children[1 - val] if 1 - val in node.children else node.children[val]
			ans = max(ans, i ^ node.val)
		return ans


class node:

	def __init__(self):
		self.c = {}
		self.end = -1

class Trie:

	def __init__(self):
		self.r = node()

	def insert(self, word, i):
		iter = self.r
		for c in word:
			if c not in iter.c:
				iter.c[c] = node()
			iter = iter.c[c]
		iter.end = i

	def search(self, word):
		iter = self.r
		for c in word:
			f = '1' if c == '0' else '0'
			if f in iter.c:
				iter = iter.c[f]
			else:
				iter = iter.c[c]
		return iter.end

class Solution:

	def max_xor(self, arr, n):
		N = max(arr)
		mask = 1
		while N:
			N //= 2
			mask += 1
		t = Trie()
		for i in range(n):
			val = bin(arr[i])[2:]
			val = val.zfill(mask)
			t.insert(val, i)
		ans = 0
		for i in range(n):
			val = bin(arr[i])[2:]
			val = val.zfill(mask)
			idx = t.search(val)
			ans = max(ans, arr[i] ^ arr[idx])
		return ans


class Solution:

	def max_xor(self, arr, n):
		ans = 0
		for i in range(31, -1, -1):
			prefixs = set([num >> i for num in arr])
			ans <<= 1
			candidate = ans + 1
			for pre in prefixs:
				if candidate ^ pre in prefixs:
					ans = candidate
					break
		return ans


class Solution:

	def max_xor(self, arr, n):
		xor = 0
		ma = 0
		s = set()
		for i in range(30, -1, -1):
			xor |= 1 << i
			amax = ma | 1 << i
			for j in range(n):
				s.add(arr[j] & xor)
			for j in s:
				if j ^ amax in s:
					ma = amax
					break
			s.clear()
		return ma