Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Consider the following function, where + denotes string concatenation.

function BinaryConcatenation(integer X, integer Y):
string binX = binary representation of X without leading zeroes
string binY = binary representation of Y without leading zeroes

string binXplusY = binX + binY
string binYplusX = binY + binX

integer XplusY = Convert binary representation binXplusY to integer
integer YplusX = Convert binary representation binYplusX to integer
return XplusY - YplusX

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$, Find the maximum value of BinaryConcatenation($A_{i}$, $A_{j}$) over all valid $i$ and $j$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the maximum of BinaryConcatenation.

------  Constraints ------
$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} < 2^{30}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (50 points): the sum of $N$ over all test cases does not exceed $1,000$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
2

2

5 9

7

1 2 4 8 16 64 128
----- Sample Output 1 ------ 
12

127
----- explanation 1 ------ 
Example case 1: The maximum value is $12 =$ BinaryConcatenation($5$, $9$). The function computes the following:
- binX = "101"
- binY = "1001"
- binXplusY = "1011001"
- binYplusX = "1001101"
- XplusY = $89$
- YplusX = $77$
- the return value is $89-77 = 12$

Example case 2: The maximum value is $127 =$ BinaryConcatenation($1$, $128$).

Difficulty: HARD
Tags: String algorithms

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
from collections import defaultdict

def binaryConcat(x, y):
	xplusy = int(bin(x)[2:] + bin(y)[2:], 2)
	yplusx = int(bin(y)[2:] + bin(x)[2:], 2)
	return abs(xplusy - yplusx)

def solution(arr):
	dmax = defaultdict(int)
	dmin = defaultdict(int)
	for i in range(len(arr)):
		blen = len(bin(arr[i])) - 2
		if dmax[blen] == 0 or dmax[blen] < arr[i]:
			dmax[blen] = arr[i]
		if dmin[blen] == 0 or dmin[blen] > arr[i]:
			dmin[blen] = arr[i]
	maxv = -float('inf')
	for i in dmax.keys():
		for j in dmin.keys():
			bcat = binaryConcat(dmax[i], dmin[j])
			if bcat > maxv:
				maxv = bcat
	return maxv
t = int(input())
for _ in range(t):
	n = input()
	arr = list(map(int, input().split()))
	print(solution(arr))


(minimumValue, maximumValue) = (-1000000000, 1000000000)

def solve(arr, N):
	(maxx, minn) = ([minimumValue] * 32, [maximumValue] * 32)
	for i in range(N):
		binaryLength = 0
		for j in range(31, -1, -1):
			bit = arr[i] & 1 << j
			if bit > 0 or binaryLength > 0:
				binaryLength += 1
		minn[binaryLength] = min(minn[binaryLength], arr[i])
		maxx[binaryLength] = max(maxx[binaryLength], arr[i])
	ans = 0
	for i in range(32):
		for j in range(32):
			if minn[j] == maximumValue or maxx[i] == minimumValue:
				continue
			value = ((1 << j) - 1) * maxx[i] - ((1 << i) - 1) * minn[j]
			ans = max(ans, value)
	print(ans)
T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	solve(arr, N)


import sys
for _ in range(int(input())):
	n = int(input())
	arr = [int(j) for j in input().split()]
	pw = [1] * 31
	for i in range(1, 31):
		pw[i] = 2 * pw[i - 1]
	mx = [0] * 32
	mn = [sys.maxsize] * 32
	for j in arr:
		l = len(bin(j)[2:])
		mx[l] = max(mx[l], j)
		mn[l] = min(mn[l], j)
	ans = 0
	for j in range(1, 32):
		for k in range(1, 32):
			x = mx[j]
			y = mn[k]
			if x == 0 or y == sys.maxsize:
				continue
			ans = max(ans, abs(x * (pw[k] - 1) - y * (pw[j] - 1)))
	print(ans)


def fun(x, minimum, y, maximum):
	a = x * 2 ** minimum - y * 2 ** maximum + (y - x)
	return a
import math
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ma = [0]
	mi = [0]
	l = 1
	for i in range(31):
		l = l * 2
		ma.append(0)
		mi.append(l)
	for j in range(n):
		ln = math.ceil(math.log(li[j] + 1) / math.log(2))
		ma[ln] = max(li[j], ma[ln])
		mi[ln] = min(li[j], mi[ln])
	for i in range(1, 32):
		if ma[i] != 0:
			x = ma[i]
			maximum = i
			break
	for i in range(31, 0, -1):
		if mi[i] != 2 ** i:
			y = mi[i]
			minimum = i
			break
	ans = fun(x, minimum, y, maximum)
	for i in range(1, 32):
		if ma[i] != 0:
			x = ma[i]
			maximum = i
			for i in range(31, 0, -1):
				if mi[i] != 2 ** i:
					y = mi[i]
					minimum = i
					ans = max(ans, fun(x, minimum, y, maximum))
	print(ans)


from math import log2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(input().split())
	if n == 1:
		print(0)
	else:
		x = [0] * 31
		y = [2 ** 30] * 31
		for i in a:
			s = bin(int(i))
			l = len(s) - 2
			x[l] = max([x[l], int(i)])
			y[l] = min([y[l], int(i)])
		ans = -1000
		for i in x:
			if i == 0:
				continue
			for j in y:
				if j == 2 ** 30:
					continue
				(pi, pj) = (int(log2(i)), int(log2(j)))
				(x1, y1) = (i, j)
				x1 = x1 << pj + 1
				y1 = y1 << pi + 1
				x1 += j
				y1 += i
				if x1 - y1 > ans:
					ans = x1 - y1
		print(ans)


def strbin(x, y):
	binx = bin(x)[2:]
	biny = bin(y)[2:]
	xplusy = binx + biny
	yplusx = biny + binx
	return int(xplusy, 2) - int(yplusx, 2)
test = int(input())
for _ in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	if n == 1:
		b.append(a[0])
	else:
		a.sort()
		if n >= 10 ** 3:
			for i in range(n - 1):
				b.append(strbin(a[n - 1], a[i]))
		else:
			for i in range(n):
				for j in range(n):
					if i == j:
						continue
					else:
						b.append(strbin(a[i], a[j]))
	print(max(b))


def ans(x, y):
	x = bin(x)[2:]
	y = bin(y)[2:]
	return int(x + y, 2) - int(y + x, 2)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 800:
		x = max([ans(i, j) for j in a for i in a])
		print(x)
	else:
		y = max(a)
		x = max([abs(ans(i, y)) for i in a])
		print(x)


import math

def leng(n):
	return math.floor(math.log(n, 2)) + 1

def fun(a, b):
	(x, y) = (leng(a), leng(b))
	aplusb = a << y | b
	bplusa = b << x | a
	return abs(aplusb - bplusa)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = -1
	if n <= 500:
		for i in range(n - 1):
			ans = [fun(arr[i], j) for j in arr[i + 1:]]
			ans_m = max(ans)
			m = max(ans_m, m)
		print(m)
	else:
		m = max(arr)
		ans = [fun(m, i) for i in arr]
		print(max(ans))


def bincon(a, b):
	X = bin(a).replace('0b', '')
	Y = bin(b).replace('0b', '')
	XpY = int(X + Y, 2)
	YpX = int(Y + X, 2)
	return max(XpY - YpX, YpX - XpY)
for _ in range(int(input())):
	n = int(input())
	llist = list(map(int, input().split()))
	ans = 0
	if n < 1000:
		for u in range(n):
			for j in range(n):
				ans = max(ans, bincon(llist[u], llist[j]))
		print(ans)
	else:
		llist.sort()
		ans = bincon(llist[0], llist[n - 1])
		for u in range(n):
			ans = max(ans, bincon(llist[u], llist[n - 1]))
		print(ans)


import math
from collections import defaultdict

def binaryconc(a, b):
	abin = bin(a).replace('0b', '')
	bbin = bin(b).replace('0b', '')
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	a1 = int(apb, 2)
	a2 = int(bpa, 2)
	return a1 - a2
t = int(input())
for i in range(0, t):
	n = int(input())
	a = [int(x) for x in input().split()][:n]
	z = []
	if n <= 500:
		for b in range(len(a)):
			for c in range(len(a)):
				z.append(binaryconc(a[b], a[c]))
		print(max(z))
	else:
		count = 0
		tmp = max(a)
		for y in range(len(a)):
			z.append(binaryconc(tmp, a[y]))
		print(max(z))


t = int(input())

def func(a, b):
	bin_a = bin(a).replace('0b', '')
	bin_b = bin(b).replace('0b', '')
	bin_X = bin_a + bin_b
	bin_y = bin_b + bin_a
	p = int(bin_X, 2)
	q = int(bin_y, 2)
	return max(p - q, q - p)
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	if n < 1000:
		for i in range(n):
			for j in range(n):
				ans = max(ans, func(a[i], a[j]))
	else:
		a = sorted(a)
		ans = func(a[0], a[n - 1])
		for i in range(n):
			ans = max(ans, func(a[i], a[n - 1]))
	print(ans)
	t -= 1


def binfun(x, y):
	binx = str(bin(x))
	binx = binx[2:]
	biny = str(bin(y))
	biny = biny[2:]
	binxpy = binx + biny
	binypx = biny + binx
	return abs(int(binxpy, 2) - int(binypx, 2))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	t = max(a)
	if n <= 500:
		for i in range(n - 1):
			for j in range(i + 1, n):
				m = max(binfun(a[j], a[i]), m)
		print(m)
	else:
		for i in range(n):
			m = max(binfun(t, a[i]), m)
		print(m)


import math
from collections import defaultdict

def binconcat(a, b):
	abin = bin(a).replace('0b', '')
	bbin = bin(b).replace('0b', '')
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	n1 = int(apb, 2)
	n2 = int(bpa, 2)
	return n1 - n2
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	binc = []
	if n <= 500:
		for i in range(n):
			for j in range(n):
				binc.append(binconcat(a[i], a[j]))
		print(max(binc))
	else:
		ans = 0
		tmp = max(a)
		for x in range(n):
			binc.append(binconcat(tmp, a[x]))
		print(max(binc))


def concat(a, b):
	anum = bin(a).replace('0b', '')
	bnum = bin(b).replace('0b', '')
	bXplusY = anum + bnum
	bYplusX = bnum + anum
	x = int(bXplusY, 2)
	y = int(bYplusX, 2)
	return x - y
t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	k = []
	if n <= 100:
		for i in range(n):
			for j in range(n):
				k.append(concat(ar[i], ar[j]))
		print(max(k))
	else:
		t = max(ar)
		for i in range(n):
			k.append(concat(t, ar[i]))
		print(max(k))


for i in range(int(input())):
	powers = [[None, None, None, None] for x in range(30)]
	n = int(input())
	nums = [int(x) for x in input().split()]
	for i in nums:
		bi_num = bin(i)[2:]
		l = len(bi_num) - 1
		if powers[l][0] == None or powers[l][0] > i:
			powers[l][0] = i
			powers[l][1] = l
		if powers[l][2] == None or powers[l][2] < i:
			powers[l][2] = i
			powers[l][3] = l
	res = 0
	for j in range(30):
		for k in range(30):
			if powers[j][2] != None and powers[k][0] != None:
				tr = powers[j][2] * 2 ** (powers[k][1] + 1) + powers[k][0] - powers[k][0] * 2 ** (powers[j][3] + 1) - powers[j][2]
				if tr > res:
					res = tr
	print(res)


def check(a, b):
	abin = bin(a).replace('0b', '')
	bbin = bin(b).replace('0b', '')
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	n1 = int(apb, 2)
	n2 = int(bpa, 2)
	return n1 - n2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	tmp = max(a)
	b = []
	if n <= 500:
		for i in range(n):
			for j in range(n):
				b.append(check(a[i], a[j]))
	else:
		for i in range(n):
			b.append(check(tmp, a[i]))
	print(max(b))


def check(a, b):
	abin = bin(a).replace('0b', '')
	bbin = bin(b).replace('0b', '')
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	n1 = int(apb, 2)
	n2 = int(bpa, 2)
	return n1 - n2
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	binc = []
	if n <= 500:
		for i in range(n):
			for j in range(n):
				binc.append(check(a[i], a[j]))
		print(max(binc))
	else:
		ans = 0
		tmp = max(a)
		for x in range(n):
			binc.append(check(tmp, a[x]))
		print(max(binc))


def binary(X, Y):
	str_x = bin(X)[2:]
	str_y = bin(Y)[2:]
	XplusY = str_x + str_y
	YplusX = str_y + str_x
	Xnew = int('0b' + XplusY, 2)
	Ynew = int('0b' + YplusX, 2)
	return abs(Xnew - Ynew)
t = int(input())
for i in range(0, t):
	n = int(input())
	list1 = list(map(int, input().split()))
	max1 = 0
	if n <= 500:
		for i in range(0, len(list1) - 1):
			for j in range(i + 1, len(list1)):
				x = binary(list1[i], list1[j])
				if x > max1:
					max1 = x
				else:
					continue
	else:
		max2 = max(list1)
		for k in range(0, len(list1)):
			x = binary(list1[k], max2)
			if x > max1:
				max1 = x
			else:
				continue
	print(max1)


def convert(a, b):
	ab = bin(a).replace('0b', '')
	ba = bin(b).replace('0b', '')
	aba = str(ab) + str(ba)
	bab = str(ba) + str(ab)
	x = int(aba, 2)
	y = int(bab, 2)
	return x - y
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	if n <= 500:
		for i in range(n):
			for j in range(n):
				b.append(convert(a[i], a[j]))
		print(max(b))
	else:
		tmp = max(a)
		for i in range(n):
			b.append(convert(tmp, a[i]))
		print(max(b))


for tcase in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	b = [a[i].bit_length() for i in range(n)]
	c = [a[i] for i in range(n) if i == 0 or i == n - 1 or b[i - 1] < b[i + 1]]
	d = [c[i].bit_length() for i in range(len(c))]
	print(max([abs((c[i] << d[j]) + c[j] - (c[j] << d[i]) - c[i]) for i in range(len(c)) for j in range(i)]))


import math

def geta(a, b, ma, mb):
	x = (a << mb) + b
	y = (b << ma) + a
	return abs(x - y)

def getn(a):
	x = math.log2(a)
	return int(x + 1)

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	v = [[] for _ in range(32)]
	for i in range(n):
		x = getn(a[i])
		v[x].append(a[i])
	for i in v:
		i.sort()
	ans = -1
	for i in range(1, 32):
		for j in range(1, 32):
			if not v[i] or not v[j]:
				continue
			ans = max(ans, geta(v[i][0], v[j][-1], i, j))
	print(ans)
t = int(input())
while t > 0:
	solve()
	t -= 1


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	d1 = {}
	d2 = {}
	for i in range(n):
		b = bin(a[i])[2:]
		lb = len(b)
		if lb not in d1:
			d1[lb] = a[i]
		else:
			d1[lb] = max(d1[lb], a[i])
	for i in range(n):
		b = bin(a[i])[2:]
		lb = len(b)
		if lb not in d2:
			d2[lb] = a[i]
		else:
			d2[lb] = min(d2[lb], a[i])
	ans = -1
	for i in d1:
		for j in d2:
			A = 2 ** j - 1
			B = 2 ** i - 1
			ans = max(abs(A * d1[i] - B * d2[j]), ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in a:
		b.append(0)
		while i > 0:
			b[-1] += 1
			i = i >> 1
	ans = -1
	if n >= 500:
		j = a.index(max(a))
		for i in range(n):
			x = a[i] * 2 ** b[j] + a[j]
			y = a[j] * 2 ** b[i] + a[i]
			ans = max(x - y, ans, y - x)
	else:
		for i in range(n):
			for j in range(i, n):
				x = a[i] * 2 ** b[j] + a[j]
				y = a[j] * 2 ** b[i] + a[i]
				ans = max(x - y, ans, y - x)
	print(ans)


import math

def bincon(a, b):
	abin = bin(a).replace('0b', '')
	bbin = bin(b).replace('0b', '')
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	A = int(apb, 2)
	B = int(bpa, 2)
	return A - B
for _ in range(int(input())):
	N = int(input())
	lon = list(map(int, input().split()))
	conli = []
	if N <= 500:
		for i in lon:
			for j in lon:
				conli.append(bincon(i, j))
		print(max(conli))
	else:
		a = max(lon)
		for i in lon:
			conli.append(bincon(a, i))
		print(max(conli))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	max_bit = [0] * 32
	min_bit = [10 ** 9] * 32
	for i in range(n):
		b = len(bin(a[i])) - 2
		max_bit[b] = max(max_bit[b], a[i])
		min_bit[b] = min(min_bit[b], a[i])
	ans = -1
	for i in range(1, 32):
		for j in range(1, 32):
			X = max_bit[i]
			Y = min_bit[j]
			if X == 0 or Y == 10 ** 9:
				continue
			else:
				d = X * (2 ** j - 1) - Y * (2 ** i - 1)
				ans = max(ans, d)
	print(ans)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	d = []
	m = 0
	ma = max(l)
	mb = bin(ma)
	mb = mb[2:]
	if n < 1000:
		for i in l:
			b = bin(i)
			d.append(b[2:])
		for i in range(n):
			for j in range(i + 1, n):
				x = d[i]
				y = d[j]
				x1 = x + y
				y1 = y + x
				x1 = int(x1, 2)
				y1 = int(y1, 2)
				if m < abs(x1 - y1):
					m = abs(x1 - y1)
		print(m)
	else:
		for i in l:
			b = bin(i)
			d.append(b[2:])
		for i in range(n):
			x = d[i]
			y = mb
			x1 = x + y
			y1 = y + x
			x1 = int(x1, 2)
			y1 = int(y1, 2)
			if m < abs(x1 - y1):
				m = abs(x1 - y1)
		print(m)


def binfun(x, y):
	binX = bin(x).replace('0b', '')
	binY = bin(y).replace('0b', '')
	binXplusY = binX + binY
	binYplusX = binY + binX
	XplusY = int(binXplusY, 2)
	YplusX = int(binYplusX, 2)
	return abs(XplusY - YplusX)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	ans = 0
	tmp = l[n - 1]
	for x in range(n):
		ans = max(ans, binfun(tmp, l[x]))
	tmp1 = l[n - 2]
	ans1 = 0
	for x in range(n):
		ans1 = max(ans1, binfun(tmp1, l[x]))
	print(max(ans, ans1))


def binfun(x, y):
	binX = bin(x).replace('0b', '')
	binY = bin(y).replace('0b', '')
	binXplusY = binX + binY
	binYplusX = binY + binX
	XplusY = int(binXplusY, 2)
	YplusX = int(binYplusX, 2)
	return abs(XplusY - YplusX)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	s = 0
	if n <= 400:
		for i in range(len(l)):
			for j in range(i + 1, len(l)):
				s = max(s, binfun(l[i], l[j]))
		print(s)
	else:
		ans = 0
		tmp = max(l)
		for x in range(n):
			ans = max(ans, binfun(tmp, l[x]))
		print(ans)


from math import log
from collections import defaultdict

def binconcat(a, b):
	return (a << binsize(b)) + b - ((b << binsize(a)) + a)

def binsize(n):
	if n == 0:
		return 0
	return int(log(n, 2)) + 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(key=lambda x: (binsize(x), -1 * x))
	dmax = defaultdict(lambda : -1)
	dmin = defaultdict()
	for i in a:
		if dmax[binsize(i)] == -1:
			dmax[binsize(i)] = i
		dmin[binsize(i)] = i
	maxsize = binsize(a[-1])
	minsize = binsize(a[0])
	ans = 0
	for i in range(minsize, maxsize + 1):
		for j in range(minsize, maxsize + 1):
			if dmax[i] != -1 and dmax[j] != -1:
				ans = max(ans, binconcat(dmax[i], dmin[j]))
	print(ans)


def BinFun(x, y):
	binx = bin(x).replace('0b', '')
	biny = bin(y).replace('0b', '')
	intxy = int(binx + biny, 2)
	intyx = int(biny + binx, 2)
	diff = abs(intxy - intyx)
	return diff
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	rarr = []
	if n < 500:
		for a in range(n):
			for b in range(n):
				rarr.append(BinFun(l[a], l[b]))
		print(max(rarr))
	else:
		ans = 0
		tmp = max(l)
		for x in range(n):
			rarr.append(BinFun(tmp, l[x]))
		print(max(rarr))


def fun(x, y):
	lx = len(bin(x)[2:])
	ly = len(bin(y)[2:])
	var = x * pow(2, ly) + y - (y * pow(2, lx) + x)
	return var
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	dic = {}
	for i in range(n):
		var = len(bin(ar[i])[2:]) - 1
		if var in dic:
			dic[var].append(ar[i])
		else:
			dic[var] = [ar[i]]
	for i in dic:
		dic[i].sort()
	m = None
	for i in dic:
		for j in dic:
			val = fun(dic[i][-1], dic[j][0])
			if m == None or m < val:
				m = val
	print(m)


def binarycon(x, y):
	binx = bin(x)[2:]
	biny = bin(y)[2:]
	binxplsy = binx + biny
	binyplsx = biny + binx
	xplsy = int(binxplsy, 2)
	yplsx = int(binyplsx, 2)
	return xplsy - yplsx
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	rarr = []
	if n < 500:
		for a in range(n):
			for b in range(n):
				rarr.append(binarycon(l[a], l[b]))
		print(max(rarr))
	else:
		ans = 0
		tmp = max(l)
		for x in range(n):
			rarr.append(binarycon(tmp, l[x]))
		print(max(rarr))


import math

def bincon(a, b):
	abin = bin(a)[2:]
	bbin = bin(b)[2:]
	apb = abin + bbin
	bpa = bbin + abin
	return abs(int(apb, 2) - int(bpa, 2))
for _ in range(int(input())):
	N = int(input())
	lon = list(map(int, input().split()))
	conli = []
	if N <= 500:
		for i in lon:
			for j in lon:
				conli.append(bincon(i, j))
		print(max(conli))
	else:
		a = max(lon)
		for i in lon:
			conli.append(bincon(a, i))
		print(max(conli))


import math

def binconcat(a, b):
	abin = bin(a).replace('0b', '')
	bbin = bin(b).replace('0b', '')
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	n1 = int(apb, 2)
	n2 = int(bpa, 2)
	return n1 - n2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	if n <= 500:
		for i in range(n):
			for j in range(n):
				l.append(binconcat(a[i], a[j]))
		print(max(l))
	else:
		ans = 0
		tmp = max(a)
		for x in a:
			l.append(binconcat(tmp, x))
		print(max(l))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var, end='\n'):
	sys.stdout.write(str(var) + end)

def outa(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(int(data())):
	n = int(data())
	arr = l()
	answer = 0
	d = dd(list)
	for i in range(n):
		for j in range(32, -1, -1):
			if arr[i] & 1 << j:
				d[j].append(arr[i])
				break
	for i in range(33):
		d[i].sort()
	for i in range(32, -1, -1):
		for j in range(32, -1, -1):
			if not d[i] or not d[j]:
				continue
			(b1, b2) = (bin(d[i][0])[2:], bin(d[j][-1])[2:])
			(t1, t2) = (int(b1 + b2, 2), int(b2 + b1, 2))
			answer = max(answer, abs(t1 - t2))
	out(answer)


import sys
from collections import defaultdict as dd
input = sys.stdin.readline

def msb(n):
	n |= n >> 1
	n |= n >> 2
	n |= n >> 4
	n |= n >> 8
	n |= n >> 16
	n |= n >> 32
	n |= n >> 64
	return n - (n >> 1)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dd(list)
	for i in a:
		d[msb(i)] += [i]
	for i in d.keys():
		d[i].sort()
	ans = -1
	for i in d.keys():
		for j in d.keys():
			if i == j and len(d[i]) < 2:
				continue
			else:
				ans = max(ans, (2 * j - 1) * d[i][-1] - (2 * i - 1) * d[j][0])
	print(ans)


def binconcat(a, b):
	abin = bin(a)
	bbin = bin(b)
	abin = abin[2:]
	bbin = bbin[2:]
	apb = str(abin) + str(bbin)
	bpa = str(bbin) + str(abin)
	n1 = int(apb, 2)
	n2 = int(bpa, 2)
	return n1 - n2
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	binc = []
	if n <= 100:
		for i in range(n):
			for j in range(n):
				binc.append(binconcat(a[i], a[j]))
		print(max(binc))
	else:
		tmp = max(a)
		for x in range(n):
			binc.append(binconcat(tmp, a[x]))
		print(max(binc))


def binConcatenate(x, y):
	x = bin(x)[2:]
	y = bin(y)[2:]
	a = int(x + y, 2)
	b = int(y + x, 2)
	return abs(a - b)
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = []
	temp = max(arr)
	if n < 500:
		for i in range(n):
			for j in range(n):
				ans.append(binConcatenate(arr[i], arr[j]))
		print(max(ans))
	else:
		for i in range(n):
			ans.append(binConcatenate(temp, arr[i]))
		print(max(ans))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	b = []
	for i in range(n):
		b.append(bin(a[i]).replace('0b', ''))
	c = b[0]
	d = b[0]
	for i in range(n):
		p = b[i] + c
		q = c + b[i]
		p = int(p, 2)
		q = int(q, 2)
		if abs(p - q) > count:
			d = b[i]
			count = abs(p - q)
	for i in range(n):
		p = b[i] + d
		q = d + b[i]
		p = int(p, 2)
		q = int(q, 2)
		if abs(p - q) > count:
			count = abs(p - q)
	print(count)


def BinaryConcatenation(X, Y):
	binX = str(bin(X).replace('0b', ''))
	binY = str(bin(Y).replace('0b', ''))
	binXplusY = binX + binY
	binYplusX = binY + binX
	XplusY = int(binXplusY, 2)
	YplusX = int(binYplusX, 2)
	return abs(XplusY - YplusX)
t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	a = -1000000
	ans = []
	if n < 500:
		for i in range(n - 1):
			for j in range(i + 1, n):
				ans.append(max(a, BinaryConcatenation(L[i], L[j])))
	else:
		m = max(L)
		a = -2147483647
		for i in L:
			ans.append(max(m, BinaryConcatenation(i, m)))
	print(max(ans))


def countbits(num):
	cnt = 0
	while num:
		num = num // 2
		cnt += 1
	return cnt
po = [1]
for i in range(1, 32):
	po.append(po[-1] * 2)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	mx = [0] * 32
	mn = [float('inf')] * 32
	for i in a:
		l = countbits(i)
		mx[l] = max(mx[l], i)
		mn[l] = min(mn[l], i)
	ans = -1
	for i in range(32):
		for j in range(32):
			x = mx[i]
			y = mn[j]
			if x != 0 and y != float('inf'):
				xminusy = x * (po[j] - 1) - y * (po[i] - 1)
				ans = max(ans, xminusy)
	print(ans)


import math
import sys
from collections import defaultdict

def bifun(a, b):
	bx = bin(a)[2:]
	by = bin(b)[2:]
	strx = bx + by
	stry = by + bx
	dx = int(strx, 2)
	dy = int(stry, 2)
	return abs(dx - dy)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = max(arr)
	max1 = 0
	if n <= 9:
		for i in range(0, n):
			for j in range(i + 1, n):
				max1 = max(max1, bifun(arr[i], arr[j]))
		print(max1)
		continue
	for i in range(n):
		max1 = max(max1, bifun(arr[i], temp))
	print(max1)


import math
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ans = [[] * i for i in range(30)]
	for i in range(n):
		b = bin(ar[i]).replace('0b', '')
		ans[len(b) - 1].append(ar[i])
	a = 0
	for i in range(30):
		if len(ans[i]) > 0:
			b1 = bin(max(ans[i])).replace('0b', '')
			for j in range(30):
				if len(ans[j]) > 0:
					b2 = bin(min(ans[j])).replace('0b', '')
					a1 = int(b1 + b2, 2)
					a2 = int(b2 + b1, 2)
					a = max(a, abs(a2 - a1))
	print(a)


from datetime import datetime
import numpy

class dicta(dict):

	def __init__(self, *args, **kwargs):
		super(dicta, self).__init__(*args, **kwargs)
		self.__dict__ = self
START_TIME = datetime.now()

def debug(**kwargs):
	return
	diff = str(datetime.now() - START_TIME)
	for (key, value) in kwargs.items():
		if isinstance(value, list):
			print(diff, key + ':')
			for item in value:
				print('\t\t\t', item)
		elif isinstance(value, dict):
			print(diff, key + ':')
			for (itemKey, item) in value.items():
				print('\t\t\t', itemKey + ': ' + str(item))
		else:
			print(diff, key + ': ' + str(value))

def printResult(result):
	if isinstance(result, list):
		print(*result)
	else:
		print(result)

def main():
	debug(status='started')
	noOfTests = int(input())
	for i in range(noOfTests):
		result = runATest(i)
		if isinstance(result, tuple):
			for line in result:
				printResult(line)
		else:
			printResult(result)
		if noOfTests > 1:
			debug(status='-------------------- finished Test#' + str(i + 1) + ' --------------------')
	debug(status='finished')
twoPow = [2 ** x - 1 for x in range(31)]

def runATest(_testIndex):
	count = int(input())
	npArray = numpy.array([int(x) for x in input().split()])
	npArray = numpy.sort(npArray)
	npArray = npArray[::-1]
	aList = npArray.tolist()
	bList = [len('{0:b}'.format(x)) for x in aList]
	markers = []
	lastLen = 0
	lastIdx = -1
	for i in range(count):
		thisLen = bList[i]
		if lastLen != thisLen:
			if i > 0 and lastIdx != i - 1:
				markers.append((aList[i - 1], lastLen))
			markers.append((aList[i], thisLen))
			lastLen = thisLen
			lastIdx = i
	if lastIdx != count - 1:
		markers.append((aList[count - 1], bList[count - 1]))
	maxValue = 0
	count = len(markers)
	for i in range(count):
		(val1, len1) = markers[i]
		for j in range(i + 1, count):
			(val2, len2) = markers[j]
			diff = abs(val1 * twoPow[len2] - val2 * twoPow[len1])
			if diff > maxValue:
				maxValue = diff
	return maxValue
main()


import sys, io, os, time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect, math, heapq
alphabet = 'abcdefghijklmnopqrstuvwxyz'
input = sys.stdin.readline
for ii in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 500:
		ans = 0
		for i in range(n):
			for j in range(n):
				b = bin(arr[i])[2:] + bin(arr[j])[2:]
				a = bin(arr[j])[2:] + bin(arr[i])[2:]
				ans = max(ans, abs(int(a, 2) - int(b, 2)))
		print(ans)
	else:
		maxe = bin(max(arr))[2:]
		ans = 0
		for i in range(n):
			a = maxe + bin(arr[i])[2:]
			b = bin(arr[i])[2:] + maxe
			ans = max(ans, abs(int(a, 2) - int(b, 2)))
		print(ans)


def bc(x, y):
	binx = bin(x).replace('0b', '')
	biny = bin(y).replace('0b', '')
	return int(binx + biny, 2) - int(biny + binx, 2)

def large(A, n):
	A.sort()
	m = -99999999999
	for i in range(n - 1):
		mx = abs(bc(A[i], A[n - 1]))
		if mx > m:
			m = mx
	print(m)

def small(A, n):
	m = -99999999999
	for i in range(n - 1):
		for j in range(i, n):
			if i != j:
				b = abs(bc(A[i], A[j]))
				if b > m:
					m = b
	print(m)
for TC in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	if n >= 1000:
		large(A, n)
	else:
		small(A, n)


from math import log2 as ln
for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	a = []
	for i in range(30):
		a.append([])
	for i in arr:
		val = int(ln(i))
		a[val].append(i)
	maxval = 0
	l = len(a)
	for i in range(l):
		if len(a[i]) > 0:
			for j in range(l):
				if len(a[j]) > 0:
					x = max(a[i])
					y = min(a[j])
					val = 2 ** (j + 1) * x + y - (2 ** (i + 1) * y + x)
					if val > maxval:
						maxval = val
	print(maxval)


def dtb(n):
	return bin(n).replace('0b', '')

def ans1(n, lst):
	res = 0
	for i in range(n):
		for j in range(i, n):
			x = lst[i]
			y = lst[j]
			binx = dtb(x)
			biny = dtb(y)
			bfx = '0b' + binx + biny
			bfy = '0b' + biny + binx
			temp = abs(int(bfx, 2) - int(bfy, 2))
			if temp >= res:
				res = temp
	return res

def ans2(n, lst):
	res = 0
	for i in range(n):
		x = lst[i]
		y = lst[n - 1]
		binx = dtb(x)
		biny = dtb(y)
		bfx = '0b' + binx + biny
		bfy = '0b' + biny + binx
		temp = abs(int(bfx, 2) - int(bfy, 2))
		if temp >= res:
			res = temp
	return res
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	if n < 1000:
		print(ans1(n, lst))
	else:
		print(ans2(n, lst))


import math
import sys
input = sys.stdin.readline

def calc(i, j):
	s1 = bin(i).replace('0b', '')
	s2 = bin(j).replace('0b', '')
	s3 = int(s1 + s2, 2)
	s4 = int(s2 + s1, 2)
	return abs(s3 - s4)
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	L.sort()
	MAX = 0
	if n < 1000:
		for i in range(n):
			for j in range(i + 1, n):
				MAX = max(MAX, calc(L[i], L[j]))
		print(MAX)
		continue
	MAX = 0
	j = L.pop(-1)
	for i in range(n - 1):
		MAX = max(MAX, calc(L[i], j))
	print(MAX)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	dp = []
	for i in range(31):
		k = []
		dp.append(k)
	for num in arr:
		for j in range(30, -1, -1):
			temp = 1 << j
			if temp & num:
				dp[j].append(num)
				break
	ans = 0
	for a in dp:
		a.sort()
	for i in range(31):
		if dp[i]:
			for j in range(31):
				if dp[j]:
					l = dp[i][-1]
					x = l << j + 1
					r = dp[j][0]
					y = r << i + 1
					a1 = x + r
					a2 = y + l
					ans = max(ans, abs(a1 - a2))
	print(ans)


def BinConcatenation(a, b):
	(a, b) = (str(bin(a)[2:]), str(bin(b)[2:]))
	(binaplusb, binbplusa) = (a + b, b + a)
	(intaplusb, intbplusa) = (int(binaplusb, 2), int(binbplusa, 2))
	return abs(intaplusb - intbplusa)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = []
	if len(arr) < 501:
		for i in range(len(arr)):
			for j in range(len(arr)):
				res.append(BinConcatenation(arr[i], arr[j]))
		print(max(res))
	else:
		(val, max_arr) = (0, max(arr))
		for i in range(len(arr)):
			res.append(BinConcatenation(max_arr, arr[i]))
		print(max(res))


from itertools import permutations
for t in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	if n < 1000:
		c = [x for x in permutations(l, 2)]
		a = []
		for x in c:
			binx = bin(x[0])[2:]
			biny = bin(x[1])[2:]
			bxpy = binx + biny
			bypx = biny + binx
			xpy = int(bxpy, 2)
			ypx = int(bypx, 2)
			if xpy > ypx:
				a.append(xpy - ypx)
		print(max(a))
	else:
		l.sort()
		m = max(l)
		binx = bin(m)[2:]
		a = 0
		for i in range(n - 2, -1, -1):
			biny = bin(l[i])[2:]
			xpy = int(binx + biny, 2)
			ypx = int(biny + binx, 2)
			res = abs(xpy - ypx)
			if res > a:
				a = res
		print(a)


from math import *

def binp(k, m):
	x = '{0:b}'.format(k)
	y = '{0:b}'.format(m)
	p = x + y
	q = y + x
	am = int(p, 2)
	an = int(q, 2)
	ans = abs(am - an)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	arr = []
	for i in range(1, n):
		x = binp(a[i], a[0])
		arr.append(x)
	for i in range(n):
		x = binp(a[i], a[1])
		arr.append(x)
	ax = max(arr)
	print(ax)


INF = float('inf')

def f(x, y):
	return abs(int(bin(x)[2:] + bin(y)[2:], 2) - int(bin(y)[2:] + bin(x)[2:], 2))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		l = len(bin(i)[2:])
		d[l] = d.get(l, [INF, -INF])
		if i < d[l][0]:
			d[l][0] = i
		if i > d[l][1]:
			d[l][1] = i
	m = 0
	for i in d.keys():
		for j in d.keys():
			m = max(m, f(d[i][0], d[j][1]), f(d[i][1], d[j][0]))
	print(m)


def conc(a, b):
	a1 = bin(a).replace('0b', '')
	b1 = bin(b).replace('0b', '')
	a1plusb1 = str(a1) + str(b1)
	a1subb1 = str(b1) + str(a1)
	a11 = int(a1plusb1, 2)
	b11 = int(a1subb1, 2)
	return a11 - b11
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	tmp = max(a)
	if n < 500:
		for i in range(n):
			for j in range(n):
				b.append(conc(a[i], a[j]))
		print(max(b))
	else:
		for i in range(n):
			b.append(conc(tmp, a[i]))
		print(max(b))