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: interview

Starter code:

Solutions:
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 = list(map(int,input().split()))
 if l==1:
  print(GLR(r))
 else:
  print((GLR(r) - GLR(l-1)))# cook your dish here


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)
 # Has the first set bit from lsb
 index = getFirstSetBitPos(n)
 # print("Index : ", index)
 # Convert the number to binary string
 binary_n_string = str(bin(n))[2:]
 # print(binary_n_string)
 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
  else:
   if 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

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)
 # Has the first set bit from lsb
 index = getFirstSetBitPos(n)
 # print("Index : ", index)
 # Convert the number to binary string
 binary_n_string = str(bin(n))[2:]
 # print(binary_n_string)
 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
  else:
   if 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()))
 sumt = 0
 # dict1 = defaultdict(int)
 # for i in range(l, r+1):
 #   val = xpr(i)
 #   if val[1] != -1 and i%2 == 0:
 #       dict1[val[1]] += 1
 #   # print(i, val)
 #   sumt += val[1]
 
 print(glr(r) - glr(l-1))
 t = t - 1

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))

# cook your dish here

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()


#!/usr/bin/python3
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()

# cook your dish here
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))

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
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 = list(map(int,input().split()))
 if l==1:
  print(GLR(r))
 else:
  print(GLR(r) - GLR(l-1))


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)
      

 

 


# cook your dish here
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))

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))

# cook your dish here
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))
 


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))


# -*- coding: utf-8 -*-
"""
Created on Sun Dec 22 22:04:23 2019

@author: user
"""
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)


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

# cook your dish here
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))

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
  # print((floor(n/a)-floor(n/(2*a)))*a)
  a*=2
 k=int(log(n,2))
 return n*(n+1)//2-int(ans)-k-1
#print(find(17))

t=int(input())
for _ in range(t):
 l,r=list(map(int,input().split()))
 print(find(r)-find(l-1))


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 -= 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 = list(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=list(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)
 else:
  if 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
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) 

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()

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()

# cook your dish here
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)