The XOR pair representation (XPR) of a positive integer $N$ is defined as a pair of integers $(A, B)$ such that:
- $1 \le A \le B \le N$
- $A \oplus B = N$
- if there is no way to choose $A$ and $B$ satisfying the above conditions, $A = B = -1$
- otherwise, the value of $A$ should be the smallest possible
These conditions uniquely define the XPR. Next, we define a function $F(N)$ = the value of $B$ in $XPR(N)$, and a function $G(L, R) = \sum\limits_{i=L}^R F(i)$.
You are given $L$ and $R$. Compute $G(L, R)$.

-----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 and only line of each test case contains two space-separated integers $L$ and $R$.

-----Output-----
For each test case, print a single line containing one integer — the value of the function $G(L, R)$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le L \le R \le 10^9$

-----Example Input-----
5
1 10
3 6
4 10
10 17
100 159

-----Example Output-----
28
9
28
79
7485

Difficulty: HARD
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
import math

def GLR(x):
	if x == 0:
		return 0
	y = x
	p = 0
	sum_a = 0
	while x >= 1:
		c = (x + 1) // 2
		sum_a += c * 2 ** p
		p += 1
		x = x - c
	sum_b = y * (y + 1) // 2 - sum_a
	ans = sum_b - (int(math.log2(y)) + 1)
	return ans
for t in range(int(input())):
	(l, r) = map(int, input().split(' '))
	ans = GLR(r) - GLR(l - 1)
	print(ans)


import math

def GLR(x):
	summation_N = x * (x + 1) // 2
	initial = x
	power = 0
	sum_A = 0
	while x >= 1:
		count = (x + 1) // 2
		sum_A += count * 2 ** power
		x = x - count
		power += 1
	sum_B = summation_N - sum_A
	ans = sum_B - (int(math.log(initial, 2)) + 1)
	return ans
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	if l == 1:
		print(GLR(r))
	else:
		print(GLR(r) - GLR(l - 1))


import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if a == 1:
		ans = -1
	else:
		ans = 0
	k = (b - a + 1) * (b + a) // 2
	ans += k
	if a % 2:
		ans -= math.ceil((b - a + 1) / 2)
	elif b % 2:
		ans -= math.ceil((b - a) / 2)
	else:
		ans -= (b - a) // 2
	i = 2 ** 30
	c = 0
	while i >= 2:
		x = b // i - (a - 1) // i
		d = x - c
		c = x
		ans -= d * i
		if i >= a and i <= b:
			ans -= 1
		i = i // 2
	print(ans)


import math
from collections import defaultdict

def IsPowerOfTwo(x):
	return x != 0 and x & x - 1 == 0

def getFirstSetBitPos(n):
	return int(math.log2(n & -n) + 1) - 1

def xpr(n):
	if IsPowerOfTwo(n):
		return (-1, -1)
	index = getFirstSetBitPos(n)
	binary_n_string = str(bin(n))[2:]
	a = ''
	b = ''
	i = 0
	for bit in reversed(binary_n_string):
		if i < index:
			a = '0' + a
			b = '0' + b
		elif i == index:
			a = '1' + a
			b = '0' + b
		elif bit == '0':
			a = '0' + a
			b = '0' + b
		else:
			a = '0' + a
			b = '1' + b
		i = i + 1
	(a, b) = (int(a, 2), int(b, 2))
	return (a, b)

def glr(x):
	tot = x * (x + 1) // 2
	lb = 0
	while x >= 1:
		tot -= int((x + 1) // 2 * 2 ** lb)
		lb += 1
		tot -= 1
		x = x / 2
	return tot
t = int(input())
while t > 0:
	(l, r) = list(map(int, input().split()))
	print(glr(r) - glr(l - 1))
	t = t - 1


def ans(p):
	pika = p * (p + 1) // 2
	tmep = 1
	while p >= 1:
		pika -= (p + 1) // 2 * tmep
		pika -= 1
		p //= 2
		tmep *= 2
	return pika
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(ans(r) - ans(l - 1))


from sys import stdin
pot2 = []
for i in range(100):
	x = 2 ** i
	if x > 10 ** 9:
		break
	pot2.append(x)
pot2 = pot2[::-1]

def tot(x):
	acum = 0
	ans = 0
	ones = 0
	aux = x * (x + 1)
	aux = aux // 2
	for i in pot2:
		y = x // i - acum
		if y >= 1:
			ones += 1
			acum += 1
			y -= 1
			aux -= i
		ans += y * i
		acum = x // i
	ans = aux - ans - ones
	return ans
T = int(stdin.readline().strip())
for case in range(T):
	(a, b) = map(int, stdin.readline().strip().split())
	print(tot(b) - tot(a - 1))


import math

def count(N):
	if N < 1:
		return 0
	total = N * (N + 1) // 2
	a = 1
	d = 2
	while N >= a:
		n = math.floor((N - a) / d) + 1
		total -= n * a + 1
		a *= 2
		d *= 2
	return total
T = int(input())
for _ in range(T):
	(L, R) = list(map(int, input().split()))
	print(count(R) - count(L - 1))


import math

def Fun(a):
	if a == 0:
		return 0
	sum_n = a * (a + 1) // 2
	ini = a
	p = 0
	anss = 0
	while a >= 1:
		c = (a + 1) // 2
		anss += c * pow(2, p)
		a = a - c
		p += 1
	dd = int(math.log2(ini))
	return sum_n - anss - dd - 1
t = int(input())
while t > 0:
	arr = list(map(int, input().split()))
	l = arr[0]
	r = arr[1]
	ans = Fun(r) - Fun(l - 1)
	print(ans)
	t = t - 1


import math

def ceil(n):
	if int(n) == n:
		return int(n)
	else:
		return int(n) + 1

def compute(n):
	if n == 0:
		return 0
	temp = int(math.log(n, 2)) + 1
	ans = n * (n + 1) // 2
	ans -= temp
	rr = 1
	while n != 0:
		ans -= ceil(n / 2) * rr
		n = n // 2
		rr = rr * 2
	return ans
t = int(input())
for i in range(t):
	(l, r) = list(map(int, input().split()))
	ans = compute(r) - compute(l - 1)
	print(ans)


def solve(a):
	b = 1
	for i in range(31):
		if a < b:
			length = i
			b >>= 1
			break
		b <<= 1
	res = a * (a + 1) // 2
	cumusum = 0
	for _ in range(length):
		n = a // b - cumusum
		res -= n * b + 1
		cumusum += n
		b >>= 1
	return res

def main():
	T = int(input())
	for _ in range(T):
		(l, r) = map(int, input().split())
		print(solve(r) - solve(l - 1))
main()


import math
t = int(input())

def glr(x):
	sigma_a = 0
	a = x
	sigma_n = x * (x + 1) // 2
	p = 0
	while x > 0:
		if x % 2 == 0:
			count = x // 2
		else:
			count = (x + 1) // 2
		sigma_a += count * 2 ** p
		x -= count
		p += 1
	sigma_b = sigma_n - sigma_a
	sigma_b = sigma_b + -1 * int(math.log(a, 2))
	return sigma_b
for i in range(t):
	(l, r) = list(map(int, input().split()))
	if l > 1:
		ans = glr(r) - glr(l - 1)
	else:
		ans = glr(r) - 1
	print(ans)


import math

def func(x):
	temp = x
	if x == 0:
		return 0
	if x == 1:
		return -1
	if x == 2:
		return -2
	count = 0
	total = x * (x + 1) // 2
	x = x + 1
	while x > 1:
		count_one = x // 2
		total -= count_one * 2 ** count
		x = x - count_one
		count += 1
	return total - math.floor(math.log(temp) / math.log(2)) - 1
t = int(input())
for _ in range(t):
	s = list(map(int, input().split()))
	(l, r) = (s[0], s[1])
	print(func(r) - func(l - 1))


import math

def xpn(n):
	sum_n = n * (n + 1) // 2
	temp = n
	sum_a = 0
	p = 0
	while n >= 1:
		c = (n + 1) // 2
		sum_a += c * 2 ** p
		n -= c
		p += 1
	sum_b = sum_n - sum_a
	b = sum_b - (int(math.log(temp, 2)) + 1)
	return b
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	if l == 1:
		m = xpn(r)
	else:
		m = xpn(r) - xpn(l - 1)
	print(m)


from math import log2

def grx(x):
	if x == 0:
		return 0
	i = x
	summation_n = x * (x + 1) // 2
	curr = (x + 1) // 2
	ans = 0
	p = 0
	while x >= 1:
		ans += 2 ** p * curr
		x -= curr
		curr = (x + 1) // 2
		p += 1
	return summation_n - ans - int(log2(i)) - 1
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(grx(r) - grx(l - 1))


from sys import stdin
import math

def glr(x):
	sum_n = x * (x + 1) // 2
	init = x
	sum_a = 0
	power = 0
	while x >= 1:
		temp = (x + 1) // 2
		sum_a += temp * pow(2, power)
		x = x - temp
		power += 1
	sum_b = sum_n - sum_a
	sum_b -= int(math.log(init, 2)) + 1
	return sum_b
t = int(stdin.readline())
while t:
	(l, r) = [int(x) for x in stdin.readline().split()]
	ans = 0
	if l == 1:
		ans = glr(r)
	else:
		ans = glr(r) - glr(l - 1)
	print(ans)
	t -= 1


import math

def xor_solution(l, r):
	sum_xors = 0
	for i in range(l, r + 1):
		if i & i - 1 == 0:
			sum_xors = sum_xors - 1
		else:
			sum_xors = sum_xors + (i & i - 1)
	return sum_xors

def sum_xor(x):
	if x == 0:
		return 0
	sum_n = x * (x + 1) // 2
	temp = x
	power2 = 1
	sum_a = 0
	while x >= 1:
		count = (x + 1) // 2
		sum_a += count * power2
		x = x - count
		power2 = power2 * 2
	sum_b = sum_n - sum_a
	return sum_b - (int(math.log2(temp)) + 1)

def main():
	test_case = int(input())
	ans = []
	while test_case > 0:
		(l, r) = list(map(int, input().split()))
		ans.append(sum_xor(r) - sum_xor(l - 1))
		test_case -= 1
	for i in ans:
		print(i)

def __starting_point():
	main()
__starting_point()


import numpy as np
from numba import njit

@njit
def solve(a):
	b = 1
	for i in range(31):
		if a < b:
			length = i
			b >>= 1
			break
		b <<= 1
	res = a * (a + 1) // 2
	cumusum = 0
	for _ in range(length):
		n = a // b - cumusum
		res -= n * b + 1
		cumusum += n
		b >>= 1
	return res

def main():
	T = int(input())
	for _ in range(T):
		(l, r) = list(map(int, input().split()))
		print(solve(r) - solve(l - 1))

def __starting_point():
	main()
__starting_point()


import sys
T = int(input())
for t in range(T):
	(L, R) = map(int, input().split(' '))
	res = int(R * (R + 1) // 2)
	res -= int(L * (L - 1) // 2) if L > 1 else 0
	s = 0
	flag = False
	n = 2
	c = 1
	while True:
		d = int((R - c) / n)
		if d <= 0:
			break
		if not flag:
			d2 = int((L - 1 - c) / n)
			if d2 <= 0:
				flag = True
			d -= d2
		s -= d * c
		n *= 2
		c *= 2
	n = 1
	while n <= R:
		if n >= L:
			s -= n + 1
		n *= 2
	print(res + int(s))


def lowest_bits(n):
	start = n
	current = 1
	total = 0
	while n > 0:
		(n, r) = divmod(n, 2)
		total += current * (n + r)
		current <<= 1
	return total
for _ in range(int(input())):
	(l, r) = list(map(int, input().strip().split()))
	total = (r - l + 1) * (r + l) // 2
	total -= lowest_bits(r)
	total += lowest_bits(l - 1)
	i = 1
	while i <= r:
		if l <= i <= r:
			total -= 1
		i <<= 1
	print(total)


import math

def g(r):
	if r == 1:
		return 1
	elif r == 0:
		return 0
	else:
		return 1 * math.ceil(r / 2) + 2 * g(math.floor(r / 2))
t = int(input())
while t != 0:
	t -= 1
	(l, r) = [int(x) for x in input().split()]
	pr = math.ceil(math.log(r, 2))
	pl = math.ceil(math.log(l, 2))
	ans = r * (r + 1) // 2 - l * (l - 1) // 2 - (g(r) - g(l - 1)) - (pr - pl)
	print(ans)


import math

def jd(x):
	n = x
	y = x * (x + 1) // 2
	ans = 0
	p = 0
	while n >= 1:
		c = (n + 1) // 2
		ans += int(c * math.pow(2, p))
		n -= c
		p += 1
	y -= ans
	y -= int(math.log2(x) + 1)
	return int(y)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	if l > 1:
		print(jd(r) - jd(l - 1))
	else:
		print(jd(r))


T = int(input())

def cal(n):
	if n <= 0:
		return 0
	ans = n * (n + 1)
	ans //= 2
	x = 1
	while n > 0:
		ans -= (n + 1) // 2 * x
		x *= 2
		n = n // 2
		ans -= 1
	return ans
for _ in range(T):
	(l, r) = map(int, input().split())
	print(cal(r) - cal(l - 1))


import math

def ans(n):
	if n == 0 or n == 1:
		return n
	m = n // 2
	if n % 2 == 0:
		return 2 * ans(m) + m
	else:
		return 2 * ans(m) + m + 1
t = int(input())
while t:
	t -= 1
	(a, b) = map(int, input().split())
	sl = a * (a - 1) // 2
	sr = b * (b + 1) // 2
	diff = sr - sl
	diff -= ans(b) - ans(a - 1)
	h = int(math.log(b, 2))
	l = -1
	if a == 1:
		l = -1
	else:
		l = int(math.log(a - 1, 2))
	temp = h - l
	diff = diff - temp
	print(diff)


def c(n):
	if n == 0:
		return 0
	return c(n // 2) + 1

def f(n):
	if n == 0:
		return 0
	ans = (n + 1) // 2
	ans += f(n // 2) * 2
	return ans
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	t = (r - l + 1) * (r + l) // 2
	x = f(r) - f(l - 1) + c(r) - c(l - 1)
	print(t - x)


from math import *

def finddiff(n):
	if n == 0:
		return 0
	if n == 1:
		return -1
	if n == 2:
		return -2
	c = 1
	res = 0
	while c <= n:
		res += (n // c - n // (2 * c)) * c
		c = c * 2
	powers = int(log(n, 2))
	return n * (n + 1) // 2 - res - (powers + 1)
t = int(input())
while t:
	t -= 1
	(l, r) = map(int, input().split())
	print(finddiff(r) - finddiff(l - 1))


from math import *

def find(n):
	if n == 0:
		return 0
	if n == 1:
		return -1
	if n == 2:
		return -2
	a = 1
	ans = 0
	while a <= n:
		ans += (floor(n / a) - floor(n / (2 * a))) * a
		a *= 2
	k = int(log(n, 2))
	return n * (n + 1) // 2 - int(ans) - k - 1
t = int(input())
for _ in range(t):
	(l, r) = list(map(int, input().split()))
	print(find(r) - find(l - 1))


import math

def howmany(n):
	total = n * (n + 1) // 2
	a = 1
	while a <= n:
		total = total - a * ((n - a) // (2 * a) + 1)
		total = total - 1
		a = a * 2
	return total
t = int(input())
for you in range(t):
	l = input().split()
	x = int(l[0])
	y = int(l[1])
	print(howmany(y) - howmany(x - 1))


from math import log2

def get_a(n):
	if n < 1:
		return 0
	if n == 1:
		return 1
	return (n + 1) // 2 + get_a(n // 2) * 2

def get(n):
	if n < 1:
		return 0
	total = n * (n + 1) // 2
	a = get_a(n)
	return total - a - int(log2(n)) - 1

def read():
	t = int(input())
	for i in range(t):
		(l, r) = list(map(int, input().strip().split()))
		print(get(r) - get(l - 1))
read()


def fun(m):
	sumi = m * (m + 1) // 2
	f = 1
	while f <= m:
		x = m // f + 1
		sumi -= 1 + f * (x // 2)
		f *= 2
	return sumi
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	print(fun(r) - fun(l - 1))


import math

def glr(x):
	suma = x * (x + 1) // 2
	initial = x
	p = 0
	sumA = 0
	while x >= 1:
		count = (x + 1) // 2
		sumA = sumA + count * 2 ** p
		x = x - count
		p = p + 1
	sumB = suma - sumA
	sumB = sumB - (int(math.log(initial, 2)) + 1)
	return sumB
t = int(input())
for i in range(t):
	(L, R) = map(int, input().split())
	if L == 1:
		y = glr(R)
	else:
		y = glr(R) - glr(L - 1)
	print(y)


inp = input
from math import ceil, log2

def extra(n, i):
	o = 1
	ans = 0
	while n > 0:
		m = ceil(n / 2)
		ans += o * m
		o = o * 2
		n = n - m
	return ans

def twos(n):
	ans = 0
	o = 1
	while n >= o:
		ans += 1
		o = o * 2
	return ans

def sm(n):
	return n * (n + 1) // 2

def f(n):
	return sm(n) - twos(n) - extra(n, 0)

def solve(l, r):
	return f(r) - f(l - 1)
for _ in range(int(inp().strip())):
	(l, r) = map(int, inp().strip().split(' '))
	print(solve(l, r))


def rec(n):
	sum1 = n * (n + 1) // 2
	p = 0
	x = n
	a = 0
	while x >= 1:
		b = (x + 1) // 2
		a = a + b * 2 ** p
		x = x - b
		p = p + 1
	sum1 = sum1 - a
	sum1 = sum1 - p
	return int(sum1)
t = int(input())
while t > 0:
	(l, r) = map(int, input().split())
	if l == 1:
		print(rec(r))
	else:
		print(rec(r) - rec(l - 1))
	t = t - 1