Due to the rise of covid-19 cases in India, this year BCCI decided to organize knock-out matches in IPL rather than a league. 
Today is matchday 4 and it is between one-time champions Rajasthan Royals and the team lead by the Youngest Captian - Delhi Capitals. As this match is very crucial, Rahul Tewatia, Rajasthan Royals all-rounder wants to hit six sixes in an over.  But he knows that he can only hit six sixes if he finds the maximum AND value that can be generated by any pair of elements from the given array. Help Tewatia to find the answer.
Note: AND is a bitwise '&' operator. 
Example 1:
Input: 
N = 4
arr[] = {4, 8, 12, 16}
Output: 8
Explanation:
Pair (8, 12) has the Maximum AND Value 8.
Example 2:
Input:
N = 4
arr[] = {4, 8, 16, 2}
Output: 0
Explanation: Maximum AND Value is 0.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function maxAND() which takes the array elements and N (size of the array) as input parameters and returns the maximum AND value generated by any pair in the array. 
Constraints:
1  ≤  N  ≤  10^{5}
1  ≤  arr[i]  ≤  10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    #Complete this function

    # Function for finding maximum AND value.

    def maxAND(self, arr,n):

        #Your code here

Solutions:
class Solution:

	def maxAND(self, arr, n):
		x = 0
		ans = 0
		for i in range(17, -1, -1):
			c = 0
			for j in range(n):
				if x & arr[j] == x and arr[j] & 1 << i:
					c += 1
				if c >= 2:
					break
			if c >= 2:
				ans += 1 << i
				x += 1 << i
		return ans


class Solution:

	def maxAND(self, arr, n):
		bits = max(arr).bit_length()
		curr = 0
		for i in range(bits, -1, -1):
			seti = 1 << i
			count = 0
			for j in range(n):
				if arr[j] & curr + seti == curr + seti:
					count += 1
			if count >= 2:
				curr += seti
		return curr


class Solution:

	def maxAND(self, arr, n):
		ans = 0
		for i in range(18, -1, -1):
			temp = []
			for a in arr:
				if a & 1 << i:
					temp.append(a)
			if len(temp) == 2:
				return temp[0] & temp[1]
			elif len(temp) > 2:
				arr = temp
				ans += 1 << i
		return ans


def count(arr, pat):
	c = 0
	for i in arr:
		if i & pat == pat:
			c += 1
	return c

class Solution:

	def maxAND(self, arr, n):
		ma = 0
		for i in range(31, -1, -1):
			if count(arr, ma | 1 << i) >= 2:
				ma |= 1 << i
		return ma


def check(res, arr):
	count = 0
	for i in range(len(arr)):
		if arr[i] & res == res:
			count += 1
	return count

class Solution:

	def maxAND(self, arr, N):
		ans = 0
		for i in range(16, -1, -1):
			res = ans | 1 << i
			x = check(res, arr)
			if x > 1:
				ans = res
		return ans


class Solution:

	def maxAND(self, arr, n):
		res = 0
		for bit in range(31, -1, -1):
			p = res | 1 << bit
			count = 0
			for i in range(n):
				if p & arr[i] == p:
					count += 1
			if count >= 2:
				res = p
		return res


class Solution:

	def maxAND(self, arr, n):
		if n == 1:
			return 0

		def checkbit(pat):
			count = 0
			for i in range(n):
				if pat & arr[i] == pat:
					count += 1
			return count
		res = 0
		for i in range(16, -1, -1):
			count = checkbit(res | 1 << i)
			if count >= 2:
				res |= 1 << i
		return res


class Solution:

	def maxAND(self, arr, n):
		x = 0
		ans = 0
		for i in range(17, -1, -1):
			c = 0
			for j in range(n):
				if x & arr[j] == x and arr[j] & 1 << i:
					c += 1
				if c >= 2:
					break
			if c >= 2:
				ans += 1 << i
				x += 1 << i
		return ans
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.maxAND(arr, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxAND(self, arr, n):
		res = 0
		for bit in range(31, -1, -1):
			count = 0
			pattern = res | 1 << bit
			for i in range(n):
				if arr[i] & pattern == pattern:
					count += 1
				if count >= 2:
					break
			if count >= 2:
				res = res | 1 << bit
		return res
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		arr = [int(x) for x in input().strip().split()]
		obj = Solution()
		print(obj.maxAND(arr, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def countBit(self, pat, arr, n):
		k = 0
		for i in arr:
			if i & pat == pat:
				k += 1
		return k

	def maxAND(self, arr, n):
		res = 0
		for i in range(31, -1, -1):
			count = self.countBit(res | 1 << i, arr, n)
			if count >= 2:
				res = res | 1 << i
		return res


class Solution:

	def maxAND(self, arr, n):

		def pat(patt, arr, n):
			co = 0
			for i in range(n):
				if patt & arr[i] == patt:
					co = co + 1
			return co
		res = 0
		for i in range(31, -1, -1):
			p = pat(res | 1 << i, arr, n)
			if p >= 2:
				res = res | 1 << i
		return res


class Solution:

	def maxAND(self, arr, n):
		res = 0
		for i in range(31, -1, -1):
			k = res | 1 << i
			cnt = 0
			for j in arr:
				if j & k == k:
					cnt += 1
			if cnt >= 2:
				res = k
		return res


class Solution:

	def maxAND(self, arr, n):

		def che(res):
			c = 0
			for i in range(n):
				if res & arr[i] == res:
					c += 1
			return c

		def solve():
			res = 0
			for i in range(31, -1, -1):
				c = che(res | 1 << i)
				if c >= 2:
					res |= 1 << i
			return res
		return solve()


from collections import defaultdict

class Solution:

	def maxAND(self, arr, n):

		def intersect(l1, l2):
			lst3 = l1.intersection(l2)
			return lst3
		present = set()
		bitset = defaultdict(list)
		maxAnd = 0
		for i in range(n):
			if arr[i] in present:
				if arr[i] > maxAnd:
					maxAnd = arr[i]
			else:
				num = arr[i]
				present.add(num)
				j = 0
				while num != 0:
					if num % 2 != 0:
						bitset[j].append(arr[i])
					j += 1
					num = num // 2
		ini = -1
		for i in range(32, -1, -1):
			if i in bitset and len(bitset[i]) >= 2:
				ini = i
				break
		if ini == -1:
			return 0
		prev_set = set(bitset[ini])
		for i in range(ini - 1, -1, -1):
			myset = intersect(prev_set, set(bitset[i]))
			if len(myset) > 2:
				prev_set = myset
			if len(myset) == 2:
				prev_set = myset
				break
		prev_set = list(prev_set)
		maxAnd = max(maxAnd, prev_set[0] & prev_set[1])
		return maxAnd


class Solution:

	def maxAND(self, arr, n):
		ans = 0
		cur = 16
		while cur >= 0:
			new = list()
			for i in arr:
				if i & 1 << cur > 0:
					new.append(i)
			if len(new) > 1:
				arr = new
				ans = ans | 1 << cur
			cur -= 1
		return ans


class Solution:

	def maxAND(self, arr, n):
		el = []
		i = 33
		while len(el) == 0 and i >= 0:
			for j in arr:
				if 1 << i & j != 0:
					el.append(j)
			if len(el) == 1:
				el = []
			i -= 1
		if len(el) == 0:
			return 0
		bits = [i + 1]
		while i >= 0:
			x = []
			for j in el:
				if 1 << i & j != 0:
					x.append(j)
			if len(x) > 1:
				el = x
				bits.append(i)
			i -= 1
		ans = 0
		for i in bits:
			ans |= 1 << i
		return ans


class Solution:

	def checkBit(self, pattern, arr, n):
		count = 0
		for i in range(0, n):
			if pattern & arr[i] == pattern:
				count += 1
		return count

	def maxAND(self, arr, n):
		res = 0
		for bit in range(16, -1, -1):
			count = self.checkBit(res | 1 << bit, arr, n)
			if count >= 2:
				res |= 1 << bit
		return res


class Solution:

	def maxAND(self, arr, n):
		ans = 0
		cur = 17
		count = 0
		while cur >= 0:
			count = 0
			for i in arr:
				if i & 1 << cur > 0 and (ans == 0 or ans & i == ans):
					count += 1
			if count > 1:
				ans = ans | 1 << cur
			cur -= 1
		return ans


class Solution:

	def maxAND(self, arr, n):
		res = 0
		for i in range(31, -1, -1):
			x = res | 1 << i
			c = 0
			for e in arr:
				if e & x == x:
					c += 1
			if c > 1:
				res = x
		return res


class Solution:

	def maxAND(self, arr, n):
		mx_and = 0
		max_bit = max(arr)
		a = max_bit.bit_length()
		for i in range(a, -1, -1):
			count = 0
			for j in arr:
				pattern = mx_and | 1 << i
				if pattern & j == pattern:
					count += 1
				if count >= 2:
					break
			if count >= 2:
				mx_and |= 1 << i
		return mx_and


class Solution:

	def maxAND(self, arr, n):
		ans = 0
		bits = 31
		while bits >= 0:
			past = ans | pow(2, bits)
			count = 0
			for i in arr:
				if i & past == past:
					count += 1
			if count >= 2:
				ans = past
			bits = bits - 1
		return ans


from itertools import combinations

class Solution:

	def maxAND(self, arr, n):
		bits = max(arr).bit_length()
		ans = 0
		curr = 0
		for i in range(bits, -1, -1):
			seti = 1 << i
			count = 0
			for j in range(n):
				if arr[j] & curr + seti == curr + seti:
					count += 1
			if count >= 2:
				curr += seti
		return curr


class Solution:

	def countBits(self, pattern, arr):
		c = 0
		for i in arr:
			if pattern & i == pattern:
				c += 1
		return c

	def maxAND(self, arr, n):
		if n <= 1:
			return 0
		res = 0
		c = 0
		for i in range(31, -1, -1):
			c = self.countBits(res | 1 << i, arr)
			if c >= 2:
				res |= 1 << i
		return res


class Solution:

	def maxAND(self, arr, n):
		mask = 0

		def count(mask):
			c = 0
			for num in arr:
				if num & mask == mask:
					c += 1
			return c
		for i in range(31, -1, -1):
			if count(mask | 1 << i) >= 2:
				mask = mask | 1 << i
		return mask


class Solution:

	def checkbit(self, pattern, arr, n):
		count = 0
		for i in range(n):
			if pattern & arr[i] == pattern:
				count = count + 1
		return count

	def maxAND(self, arr, n):
		res = 0
		for i in range(31, -1, -1):
			count = self.checkbit(res | 1 << i, arr, n)
			if count >= 2:
				res = res | 1 << i
		return res