An array, $\mbox{A}$, is defined as follows: 

$A_0=0$
$A_x=A_{x-1}\oplus x$ for $x>0$, where $\oplus$ is the symbol for XOR

You will be given a left and right index $\mbox{l r}$.  You must determine the XOR sum of the segment of $\mbox{A}$ as $A[l]\oplus A[l+1]\oplus ...\oplus A[r-1]\oplus A[r]$. 

For example, $A=[0,1,3,0,4,1,7,0,8]$.  The segment from $l=1$ to $r=4$ sums to $1\oplus3\oplus0\oplus4=6$. 

Print the answer to each question.

Function Description  

Complete the xorSequence function in the editor below.  It should return the integer value calculated.  

xorSequence has the following parameter(s):  

l: the lower index of the range to sum  
r: the higher index of the range to sum  

Input Format

The first line contains an integer $\textit{q}$, the number of questions. 

Each of the next $\textit{q}$ lines contains two space-separated integers, $l\left[i\right]$ and $r[i]$, the inclusive left and right indexes of the segment to query.

Constraints

$1\leq q\leq10^5$ 

 $1\leq l[i]\leq r[i]\leq10^{15}$  

Output Format

On a new line for each test case, print the XOR-Sum of $\mbox{A}$'s elements in the inclusive range between indices $l\left[i\right]$ and $r[i]$.

Sample Input 0
3
2 4
2 8
5 9

Sample Output 0
7
9
15

Explanation 0

The beginning of our array looks like this:
 $A=[0,1,3,0,4,1,7,0,8,1,11,...]$

Test Case 0: 

$3\oplus0\oplus4=7$

Test Case 1: 

$3\oplus0\oplus4\oplus1\oplus7\oplus0\oplus8=9$

Test Case 2: 

$1\oplus7\oplus0\oplus8\oplus1=15$

Sample Input 1
3
3 5
4 6
15 20

Sample Output 1
5
2
22

Explanation 1

$A=[0,1,3,0,4,1,7,0,8,1,11,0,12,1,15,0,16,1,19,0,20,1,23,0,24,1,...]$.  Perform the xor sum on each interval: 

$3-5:0\oplus4\oplus1=5$ 

$4-6:4\oplus1\oplus7=2$ 

$15-20:0\oplus16\oplus1\oplus19\oplus0\oplus20=22$

Source: hackerrank | Difficulty: MEDIUM
Tags: Bit manipulation


Solutions:
import sys

def x(a):
	res = [a, 1, a + 1, 0]
	return res[a % 4]

def y(a):
	if a % 2 == 0:
		return x(a // 2) << 1
	else:
		r = 0
		if (a + 1) % 4 == 2:
			r = 1
		return (x(a // 2) << 1) + r
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(y(R) ^ y(L - 1))


import sys

def fromzero(n):
	return [n, n, 2, 2, n + 2, n + 2, 0, 0][n % 8]
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(fromzero(R) ^ fromzero(L - 1))


from functools import reduce

def trivial_solution(L, R):
	A = [0]
	for i in range(1, R + 1):
		A.append(A[i - 1] ^ i)
	return reduce(lambda x, y: x ^ y, A[L:R + 1], 0)

def better_solution(L, R):
	return B[L - 1] ^ B[R]

def solution(L, R):

	def get_val(n):
		lookup = [n, n, 2, 2, n + 2, n + 2, 0, 0]
		m = n % 8
		return lookup[m]
	return get_val(L - 1) ^ get_val(R)

def test():
	import random
	for i in range(1000):
		L = random.randint(1, 1000)
		R = random.randint(L, 1000)
		t_sol = trivial_solution(L, R)
		b_sol = solution(L, R)
		assert t_sol == b_sol, (t_sol, b_sol)
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().strip().split())
	print(solution(L, R))


import sys

def xorsumpair(n):
	return xorsum(n // 2) * 2

def xorsum(n):
	if n % 2 == 1:
		return 1 if n % 4 == 1 else 0
	else:
		return n if n % 4 == 0 else n + 1
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	if R % 2 == 0:
		ret = xorsumpair(R) ^ xorsumpair(L - 1)
	else:
		ret = xorsumpair(R) ^ xorsumpair(L - 1) ^ (xorsum(R) ^ xorsum(L - 1))
	if (L - R + 1) % 2 != 0:
		ret ^= xorsum(L - 1)
	print(ret)


import sys

def calc_a(n):
	bits = [int(digit) for digit in bin(n)[2:]]
	a_n = 0
	is_even = bits[-1] == 0
	ones = n % 2 == 1 and (n - 1) // 2 % 2 == 0 or (n % 2 == 0 and (n - 1) // 2 % 2 == 0)
	for bit in bits[:-1]:
		if bit and is_even:
			a_n = a_n << 1
			a_n |= 1
		else:
			a_n = a_n << 1
	if ones:
		a_n = a_n << 1
		a_n |= 1
	else:
		a_n = a_n << 1
	return a_n

def xor_sum(n):
	bits = [int(digit) for digit in bin(n)[2:]]
	return calc_a(n >> 1) << 1 | (n % 2 == 1 and (n - 1) // 2 % 2 == 0)
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(xor_sum(R) ^ xor_sum(L - 1))


def solve():
	left_side = 0
	if (L + 1) % 4 == 0:
		ans = 2
		left_side = L + 5
	if L % 4 == 0:
		ans = 2
		left_side = L + 4
	if (L + 3) % 4 == 0:
		ans = L + 1
		left_side = L + 3
	if (L + 2) % 4 == 0:
		ans = L + 1
		left_side = L + 2
	right_side = 0
	if (R + 1) % 4 == 0:
		ans = ans ^ 2
		right_side = R - 3
	if (R - 2) % 4 == 0:
		ans = ans ^ 2
		right_side = R - 2
	if (R - 1) % 4 == 0:
		ans = ans ^ R
		right_side = R - 1
	if R % 4 == 0:
		ans = ans ^ R
		right_side = R
	diff = (right_side - left_side) / 4
	if diff % 2 != 0:
		ans = ans ^ 2
	return ans
T = int(input())
for _ in range(T):
	(L, R) = map(int, input().split())
	print(solve())


import sys, math

def getAx(x):
	r = (x + 1) % 4
	if x == 0 or r == 0:
		return 0
	if r == 1:
		return x
	if r == 2:
		return 1
	if r == 3:
		return x + 1
Q = int(input().strip())
for q in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	l = math.floor(L / 4) * 4
	if l < L:
		l += 4
	r = math.floor(R / 4) * 4 - 2
	if l >= r:
		xor_sum = 0
		for i in range(L, R + 1):
			xor_sum ^= getAx(i)
		print(xor_sum)
	else:
		xor_sum = 0
		groups = (r - l + 2) / 4
		if groups % 2 != 0:
			xor_sum = 2
		for i in range(L, l):
			xor_sum ^= getAx(i)
		for i in range(r + 1, R + 1):
			xor_sum ^= getAx(i)
		print(xor_sum)


import sys
Q = int(input().strip())

def xori(x):
	if x % 4 == 0:
		return x
	elif x % 4 == 1:
		return 1
	elif x % 4 == 2:
		return x + 1
	else:
		return 0

def xorii(x):
	if x % 2 == 0:
		return xori(x // 2) * 2
	else:
		return xori(x // 2) * 2 + int(x // 2 % 2 == 0)
for a0 in range(Q):
	(l, r) = input().strip().split(' ')
	(l, r) = [int(l), int(r)]
	print(xorii(l - 1) ^ xorii(r))


def xorList(n):
	value = (n + 1) // 2 & 1
	mult = 2
	while n >= mult:
		ones = n % (2 * mult) + 1 - mult
		if ones >= 1 and ones & 1:
			value += mult
		mult *= 2
	return value

def xorAlt(n):
	value = xorList(n >> 1) << 1
	if n & 1 and (n + 1) // 2 & 1:
		return value + 1
	else:
		return value
for _ in range(int(input())):
	(a, b) = [int(i) for i in input().strip().split()]
	print(xorAlt(a - 1) ^ xorAlt(b))


import sys

def xorcums(n):
	ans = xorints(n // 2 + 1) << 1
	if n % 4 == 1:
		ans ^= 1
	return ans

def xorints(n):
	ans = 0
	while n != 0:
		lowpow2 = n & ~(n - 1)
		prefix = n - lowpow2
		if lowpow2 == 1:
			ans ^= prefix
		elif lowpow2 == 2:
			ans ^= 1
		n = prefix
	return ans
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(xorcums(R) ^ xorcums(L - 1))


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	xor = 0
	temp = R
	if (R - L + 1) % 2:
		temp -= 1
	if (L + 1) % 8 == 1:
		if temp % 8 == 7:
			xor = 0
		elif temp % 8 == 5:
			xor = temp + 2
		elif temp % 8 == 3:
			xor = 2
		elif temp % 8 == 1:
			xor = temp
	elif (L + 1) % 8 == 3:
		if temp % 8 == 7:
			xor = L + 1 - 2
		elif temp % 8 == 5:
			xor = temp + 2 ^ L + 1 - 2
		elif temp % 8 == 3:
			xor = 2 ^ L + 1 - 2
		elif temp % 8 == 1:
			xor = temp ^ L + 1 - 2
	elif (L + 1) % 8 == 5:
		if temp % 8 == 7:
			xor = 2
		elif temp % 8 == 5:
			xor = temp + 2 ^ 2
		elif temp % 8 == 3:
			xor = 0
		elif temp % 8 == 1:
			xor = temp ^ 2
	elif (L + 1) % 8 == 7:
		if temp % 8 == 7:
			xor = L + 1
		elif temp % 8 == 5:
			xor = temp + 2 ^ L + 1
		elif temp % 8 == 3:
			xor = 2 ^ L + 1
		elif temp % 8 == 1:
			xor = temp ^ L + 1
	elif (L + 1) % 8 == 2:
		if temp % 8 == 0:
			xor = L + 1 - 2 ^ temp
		elif temp % 8 == 6:
			xor = L + 1 - 2
		elif temp % 8 == 4:
			xor = temp + 2 ^ L + 1 - 2
		elif temp % 8 == 2:
			xor = 2 ^ L + 1 - 2
	elif (L + 1) % 8 == 4:
		if temp % 8 == 0:
			xor = 2 ^ temp
		elif temp % 8 == 6:
			xor = 2
		elif temp % 8 == 4:
			xor = 2 ^ temp + 2
		elif temp % 8 == 2:
			xor = 0
	elif (L + 1) % 8 == 6:
		if temp % 8 == 0:
			xor = temp ^ L + 1
		elif temp % 8 == 6:
			xor = L + 1
		elif temp % 8 == 4:
			xor = temp + 2 ^ L + 1
		elif temp % 8 == 2:
			xor = 2 ^ L + 1
	if (L + 1) % 8 == 0:
		if temp % 8 == 0:
			xor = temp
		elif temp % 8 == 6:
			xor = 0
		elif temp % 8 == 4:
			xor = 2 + temp
		elif temp % 8 == 2:
			xor = 2
	if (R - L + 1) % 2:
		if R % 4 == 3:
			xor ^= 0
		elif R % 4 == 2:
			xor ^= R + 1
		elif R % 4 == 1:
			xor ^= 1
		elif R % 4 == 0:
			xor ^= R
	print(xor)


import sys
data = []
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	data.append((L, R))
for (l, r) in data:
	if l % 4 == 0:
		l1 = l // 4
	else:
		l1 = l // 4 + 1
	r1 = r // 4
	if (r1 - l1) % 2 == 0:
		result = 0
	else:
		result = 2
	for i in range(l, l1 * 4):
		if i % 4 == 0:
			result = result ^ i
		if i % 4 == 1:
			result ^= 1
		if i % 4 == 2:
			result ^= i + 1
		if i % 4 == 3:
			result ^= 0
	for i in range(r1 * 4, r + 1):
		if i % 4 == 0:
			result = result ^ i
		if i % 4 == 1:
			result ^= 1
		if i % 4 == 2:
			result ^= i + 1
		if i % 4 == 3:
			result ^= 0
	print(result)


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	a = L // 4 * 4 + 4
	b = R // 4 * 4
	c = (b - a) // 4 % 2
	if c == 1:
		xor = 2
	else:
		xor = 0
	d = []
	for x in range(L, a):
		if x % 4 == 0:
			d.append(x)
		elif x % 4 == 1:
			d.append(1)
		elif x % 4 == 2:
			d.append(x + 1)
		elif x % 4 == 3:
			d.append(0)
	for x in range(b, R + 1):
		if x % 4 == 0:
			d.append(x)
		elif x % 4 == 1:
			d.append(1)
		elif x % 4 == 2:
			d.append(x + 1)
		elif x % 4 == 3:
			d.append(0)
	for x in d:
		xor ^= x
	print(xor)


f = lambda x, m: (0, x, 1, x + 3)[m]
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = [int(x) for x in input().strip().split(' ')]
	(dl, l) = divmod(L + 1, 4)
	(dr, r) = divmod(R + 1, 4)
	s = 0
	if dl == dr:
		dl *= 4
		while l <= r:
			s ^= f(dl, l)
			l += 1
	else:
		dl *= 4
		dr *= 4
		L += (4 - l) % 4
		while 0 < l <= 3:
			s ^= f(dl, l)
			l += 1
		R -= r % 4
		while 0 < r <= 3:
			s ^= f(dr, r)
			r -= 1
		if (R - L) // 4 % 2 != 0:
			s ^= 2
	print(s)


def FindSum(num):
	m = num % 4
	if m == 0:
		return num
	elif m == 1:
		return num ^ num - 1
	elif m == 2:
		return num ^ num - 1 ^ num - 2
	else:
		return 0

def FindOddEvenSum(num):
	m = num % 8
	if m == 6 or m == 7:
		return 0
	elif m == 0 or m == 1:
		return num
	elif m == 2 or m == 3:
		return num - 2 ^ num
	elif m == 4 or m == 5:
		return num - 4 ^ num - 2 ^ num
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	length = R - L + 1
	start = 0
	if length % 2 == 0:
		L += 1
	else:
		start = FindSum(L - 1)
	print(start ^ FindOddEvenSum(L - 2) ^ FindOddEvenSum(R))


import sys

def __sigma_xor(start_basecamp, destination):
	if start_basecamp > destination:
		return 0
	if start_basecamp == destination:
		return start_basecamp
	value = start_basecamp
	result = start_basecamp
	for val in range(start_basecamp + 1, destination + 1):
		value = value ^ val
		result = result ^ value
	return result

def question(L, R):
	first_basecamp = L // 8 * 8
	next_basecamp = first_basecamp + 8
	if next_basecamp >= R:
		result = __sigma_xor(first_basecamp, L - 1) ^ __sigma_xor(first_basecamp, R)
		return result
	result = __sigma_xor(first_basecamp, L - 1) ^ __sigma_xor(first_basecamp, next_basecamp - 1)
	last_basecamp = R // 8 * 8
	result = result ^ __sigma_xor(last_basecamp, R)
	return result
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(question(L, R))


def __sigma_xor(start_basecamp, destination):
	if start_basecamp > destination:
		return 0
	if start_basecamp == destination:
		return start_basecamp
	value = start_basecamp
	result = start_basecamp
	for val in range(start_basecamp + 1, destination + 1):
		value = value ^ val
		result = result ^ value
	return result

def question(L, R):
	first_basecamp = L // 8 * 8
	next_basecamp = first_basecamp + 8
	if next_basecamp >= R:
		result = __sigma_xor(first_basecamp, L - 1) ^ __sigma_xor(first_basecamp, R)
		return result
	result = __sigma_xor(first_basecamp, L - 1) ^ __sigma_xor(first_basecamp, next_basecamp - 1)
	last_basecamp = R // 8 * 8
	result = result ^ __sigma_xor(last_basecamp, R)
	return result
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(question(L, R))


import sys
import math

def getArVal(i):
	i4 = i % 4
	if i4 == 0:
		return i
	elif i4 == 1:
		return 1
	elif i4 == 2:
		return i + 1
	else:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	seqXor = 0
	l4 = L % 4
	r4 = R % 4
	for i in range(4 - l4):
		seqXor ^= getArVal(L + i)
	start = L + (4 - l4)
	end = R - r4
	numBlocks = math.floor((end - start) / 4)
	if numBlocks % 2:
		seqXor ^= 2
	for i in range(r4 + 1):
		seqXor ^= getArVal(R - i)
	print(seqXor)


import sys

def A(n):
	o = n % 8
	if o == 0 or o == 1:
		return n
	if o == 2 or o == 3:
		return 2
	if o == 4 or o == 5:
		return 2 + n
	else:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(A(R) ^ A(L - 1))


import sys

def f(a):
	ar = [a, 1, a + 1, 0]
	return ar[a % 4]

def g(a, b):
	if (b - a + 1) % 2 > 0:
		return f(b) ^ g(a, b - 1)
	p = a + 1
	if p & 2 == 2:
		p += 2
	q = b
	if q & 2 == 0:
		q -= 2
	off = 0
	if q >= p and ((q - p) // 2 + 1) // 2 % 2 == 1:
		off = 2
	res = off
	for i in range(a + 1, p, 2):
		res ^= i
	for i in range(q + 2, b + 1, 2):
		res ^= i
	return res
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	x = g(L, R)
	print(x)


import sys

def hval(i):
	n = int(i / 4)
	m = i % 4
	if n % 2 == 0:
		if m > 1:
			return 2
		else:
			return 8 * int(n / 2) + m
	elif m > 1:
		return 0
	else:
		return 8 * int(n / 2) + 6 + m
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	rval = hval(R)
	if L > 0:
		rval ^= hval(L - 1)
	print(rval)


import sys

def running_xor_acc_to(N):
	return {0: N, 1: N, 2: 2, 3: 2, 4: N + 2, 5: N + 2, 6: 0, 7: 0}[N % 8]
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(running_xor_acc_to(R) ^ running_xor_acc_to(L - 1))


def xor_sum(n):
	if n & 1:
		return 1 ^ n >> 1 & 1
	else:
		return n ^ n >> 1 & 1
Q = int(input())
for q in range(Q):
	(L, R) = map(int, input().split())
	if R & 1:
		x = L - 1
		out = (xor_sum(R >> 1) ^ xor_sum(x >> 1)) << 1 ^ (R ^ x) >> 1 & 1
	else:
		out = (xor_sum(R >> 1) ^ xor_sum(L >> 1)) << 1
	if (~R ^ L) & 1:
		out ^= xor_sum(L)
	print(out)


import sys
import math

def x_gen_bf():
	yield 0
	(i, v) = (0, 0)
	while True:
		yield v
		i += 1
		v ^= i

def x_gen():
	v = 0
	while True:
		yield 0
		yield v
		yield 1
		yield (v + 3)
		v += 4

def solve_bf(l, r):
	rval = 0
	for (i, v) in enumerate(x_gen()):
		if i >= l and i <= r:
			rval ^= v
		elif i > r:
			break
	return rval

def test2(l, r):

	def block_size(bit_num):
		return pow(2, bit_num)

	def block_offset(bit_num, n):
		return n % block_size(bit_num)

	def is_zero_block(bit_num, n):
		v = n // block_size(bit_num)
		if v % 2:
			return False
		return True

	def full_blocks(bit_num, n):
		return n // (2 * block_size(bit_num))

	def max_bit_num(n):
		return int(math.log(n, 2))
	rval = 0
	l -= 1
	(mbnl, mbnr) = (max_bit_num(l), max_bit_num(r))
	for bit_num in range(mbnr + 1):
		lcnt = 0
		if bit_num <= mbnl:
			(size, offset) = (block_size(bit_num), block_offset(bit_num, l))
			if not is_zero_block(bit_num, l):
				lcnt = offset + 1
			(size, offset) = (block_size(bit_num), block_offset(bit_num, r))
			lcnt += full_blocks(bit_num, l) * block_size(bit_num)
		rcnt = 0
		if not is_zero_block(bit_num, r):
			rcnt = offset + 1
		rcnt += full_blocks(bit_num, r) * block_size(bit_num)
		cnt = rcnt - lcnt
		if cnt % 2:
			rval += pow(2, bit_num)
	return rval

def solve(l, r):
	(kl, il) = ((l + 1) // 4, (l + 1) % 4)
	(kr, ir) = ((r + 1) // 4, (r + 1) % 4)
	full_blocks = kr - kl
	if full_blocks:
		full_blocks -= 1
	rval = 0
	if full_blocks % 2:
		rval ^= 2
	al = (0, 4 * kl, 1, 4 * kl + 3)
	ar = (0, 4 * kr, 1, 4 * kr + 3)
	if kl == kr:
		for v in al[il:ir + 1]:
			rval ^= v
	else:
		for v in al[il:]:
			rval ^= v
		for v in ar[:ir + 1]:
			rval ^= v
	return rval

def run():
	Q = int(input().strip())
	for a0 in range(Q):
		(L, R) = input().strip().split(' ')
		(L, R) = [int(L), int(R)]
		print(solve(L, R))

def test(N):
	for (i, v) in enumerate(x_gen_bf()):
		print(v, end=' ')
		if i == N:
			break
	print()
run()


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	Left = L
	if Left % 4:
		Left += 4 - Left % 4
	Right = R + 1
	Right = Right - Right % 4
	Right = max(Right, Left)
	answer = Right - Left
	if Right > Left:
		answer = answer // 4
		answer = answer % 2
		answer = answer * 2
	else:
		answer = 0
	if L < Left:
		if (L - 1) % 4 == 0:
			answer = answer ^ L + 1
		elif (L - 2) % 4 == 0:
			answer = answer ^ L + 1
	if R + 1 > Right:
		if R % 4 == 0:
			answer = answer ^ R
		elif (R - 1) % 4 == 0:
			answer = answer ^ R
		elif (R - 2) % 4 == 0:
			answer = answer ^ R - 2 ^ 1 ^ R + 1
	print(answer)


import sys
from functools import reduce
from operator import __xor__

def xor_series(series):
	return reduce(__xor__, series, 0)

def xor(i, j):
	x = i - i % 4
	y = j - j % 4
	xseries = [x, 1, x + 3, 0]
	yseries = [y, 1, y + 3, 0]
	basket = ((y - x + 4) // 4 & 1) * 2
	rem = xseries[:i % 4] + yseries[j % 4 + 1:]
	return basket ^ xor_series(rem)
lines = [line.strip() for line in sys.stdin]
ranges = [[int(a) for a in line.split(' ')] for line in lines[1:]]
for r in ranges:
	print(xor(*r))


def A(x):
	return [x, 1, x + 1, 0][x & 3]

def B(x):
	return [x, 2, x + 2, 0][x >> 1 & 3]
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	if (l ^ r) & 1:
		print(B(l - 1) ^ B(r))
	else:
		print(B(l - 1) ^ B(r - 1) ^ A(r))


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	x = [0]
	ans = 0
	i = L
	if L == R:
		if L % 2 == 1:
			print(0)
		else:
			print(L)
		continue
	if L % 16 == 0 and R % 16 == 0:
		print(R)
		continue
	while (i + 1) % 16 != 0 and i <= R:
		t = 0
		if i % 4 == 0:
			t = int(i)
		elif i % 4 == 2:
			t = i + 1
		elif i % 4 == 1:
			t = 1
		ans ^= t
		i += 1
	if L // 16 < R // 16:
		i = R // 16 * 16
		while i <= R:
			t = 0
			if i % 4 == 0:
				t = i
			elif i % 4 == 2:
				t = i + 1
			elif i % 4 == 1:
				t = 1
			ans ^= t
			i += 1
	print(ans)


import sys

def a(top):
	if top % 2 == 1:
		return (top // 2 + 1) % 2
	x = top + 1
	return x ^ (x // 2 + 1) % 2
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	z = (R + 1 - L) // 2
	res = a(L) if (R - L) % 2 == 0 else 0
	if R % 2 == 1 and z % 2 == 1:
		res ^= 1
	res ^= 2 * (a(R // 2) ^ a(R // 2 - z))
	print(res)


def calc(n):
	if n % 4 == 0:
		return n
	elif n % 4 == 1:
		return 1
	elif n % 4 == 2:
		return n + 1
	else:
		return 0
T = int(input())
for Ti in range(T):
	(L, R) = [int(v) for v in input().split()]
	LR = L // 4 * 4 + 4
	RL = R // 4 * 4
	r = 0
	for i in range(L, LR):
		r ^= calc(i)
	for i in range(RL, R + 1):
		r ^= calc(i)
	cycles = (RL - LR) // 4
	if cycles % 2 == 1:
		r ^= 2
	print(r)


def quicksum(left, right):
	(lrem, rrem) = (left % 4, right % 4)
	(s4, e4) = (0, 0)
	if lrem == 0:
		head = 0
		s4 = left
	elif lrem == 1:
		head = left + 1
		s4 = left + 3
	elif lrem == 2:
		head = left + 1
		s4 = left + 2
	else:
		head = 0
		s4 = left + 1
	if rrem == 0:
		tail = right
		e4 = right - 1
	elif rrem == 1:
		tail = right
		e4 = right - 2
	elif rrem == 2:
		tail = 2
		e4 = right - 3
	else:
		tail = 0
		e4 = right
	fourples = (e4 - s4 + 1) // 4
	if fourples % 2 == 0:
		return head ^ tail
	return head ^ 2 ^ tail
Q = int(input().strip())
for q in range(0, Q):
	(L, R) = map(int, input().strip().split(' '))
	print(quicksum(L, R))


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	Li = L & ~3
	Ri = R + 4 & ~3
	ans = Ri - Li >> 1 & 2
	ALi = Li
	while Li < L:
		ans ^= ALi
		Li += 1
		ALi ^= Li
	ARi = Ri
	while R < Ri - 1:
		ARi ^= Ri
		Ri -= 1
		ans ^= ARi
	print(ans)


import sys

def Ax(x):
	if x == 0:
		return 0
	elif x == 1:
		return 1
	elif x == 2:
		return 3
	elif x == 3:
		return 0
	c = len(bin(x)) - 3
	d = 1 << c
	if x % 2:
		return Ax(x - d)
	else:
		return d + Ax(x - d)
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	s = 0
	if (R - L) % 2 == 0:
		s = Ax(L)
		last = L % 2
		nu = (R - L) // 2
		s ^= ((Ax(R >> 1) ^ Ax(L >> 1)) << 1) + nu * last % 2
	else:
		last = (L + 1) % 2
		nu = (R - L + 1) // 2
		s ^= ((Ax(R >> 1) ^ Ax(L - 1 >> 1)) << 1) + nu * last % 2
	print(s)


import sys
from operator import xor
from functools import reduce

def xor_intervl(L, R):
	(kL, rL) = divmod(L, 4)
	(kR, rR) = divmod(R, 4)
	intvlL = [4 * kL, 1, 4 * (kL + 1) - 1, 0]
	intvlR = [4 * kR, 1, 4 * (kR + 1) - 1, 0]
	mid = [2 * ((kR - kL - 1) % 2)]
	intvl = intvlL[rL:] + mid + intvlR[:rR]
	return reduce(xor, intvlL[rL:] + mid + intvlR[:rR])
Q = int(input().strip())
LR = []
for q in range(Q):
	(L, R) = input().strip().split(' ')
	LR.append((int(L), int(R) + 1))
for i in range(Q):
	print(xor_intervl(*LR[i]))


import sys
Q = int(input().strip())
for k in range(Q):
	xorval = 0
	a = [0]
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	i = L
	while i < R + 1:
		if i % 4 == 0 and i + 4 <= R:
			temp = (R - i) // 4
			if temp % 2 != 0:
				xorval ^= 2
			i += temp * 4 - 1
		elif i % 4 == 0 and i + 4 > R:
			xorval ^= i
		elif (i - 1) % 4 == 0:
			xorval ^= 1
		elif (i - 2) % 4 == 0:
			xorval ^= i + 1
		i += 1
	print(xorval)


t = int(input().strip())
for test in range(t):
	(L, R) = map(int, input().strip().split())
	if (R - L) % 2 == 0:
		a = [R, 1, R + 1, 0]
		xor = a[R % 4]
		R -= 1
	else:
		xor = 0
	L += 1
	while L <= R and L // 2 % 4 != 0:
		xor ^= L
		L += 2
	while L <= R and R // 2 % 4 != 3:
		xor ^= R
		R -= 2
	print(xor)


def xor_sequence(l, r, result):
	for i in range(l, r):
		if i == 0 or (i + 1) % 4 == 0:
			result ^= 0
		elif (i - 1) % 4 == 0:
			result ^= 1
		elif i % 4 == 0:
			result ^= i
		else:
			result ^= i + 1
	return result
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	l_div_4 = L + (4 - (L + 1) % 4)
	r_div_4 = R - (R + 1) % 4
	result = xor_sequence(L, l_div_4, xor_sequence(r_div_4, R + 1, 0))
	print(result if (r_div_4 - l_div_4) // 4 % 2 == 0 else result ^ 2)


def xors(x):
	r = (x & 7) >> 1
	if r == 0:
		return x
	if r == 1:
		return 2
	if r == 2:
		return x + 2
	return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(xors(L - 1) ^ xors(R))


import sys

def xorEveryOther(n):
	D = n & 6
	if D == 0:
		return n
	elif D == 2:
		return 2
	elif D == 4:
		return n + 2
	return 0

def solve(L, R):
	return xorEveryOther(R) ^ xorEveryOther(L - 1)
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(solve(L, R))


def xor(num):
	res = 0
	for i in range(0, (num + 1) % 8, 2):
		res ^= num - i
	return res
Q = int(input())
for i in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print('{}'.format(xor(L - 1) ^ xor(R)))


import sys

def get_val(v):
	facs = [(1, 0), (0, 1), (1, 1), (0, 0)]
	idx = v % 4
	val = v * facs[idx][0] + facs[idx][1]
	return val
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	xx = 0
	if R - L < 4:
		for i in range(L, R + 1):
			v = get_val(i)
			xx = xx ^ v
	else:
		l = (L + 4) // 4
		r = R // 4
		for i in range(L, 4 * l):
			v = get_val(i)
			xx = xx ^ v
		for i in range(4 * r, R + 1):
			v = get_val(i)
			xx = xx ^ v
		ns = r - l
		if ns % 2:
			xx = xx ^ 2
	print(xx)


def tab_val(n):
	return [n, 1, n + 1, 0][n % 4]

def answer(a, b):
	res = 0
	while a <= b and a % 4 != 0:
		res ^= tab_val(a)
		a += 1
	while a <= b and b % 4 != 3:
		res ^= tab_val(b)
		b -= 1
	slice_number = (b - a + 1) // 4 if a < b else 0
	if slice_number % 2:
		res ^= 2
	return res
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(answer(L, R))


def val(x):
	pos = x % 4
	return ([x, 1, x + 1, 0][pos], pos)
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	xor = 0
	while L <= R:
		(v, pos) = val(L)
		if pos == 3:
			break
		xor ^= v
		L += 1
	n_seq = (R - L + 1) // 4
	if n_seq & 1:
		xor ^= 2
	if L <= R:
		while 1:
			(v, pos) = val(R)
			if pos == 2:
				break
			xor ^= v
			R -= 1
	print(xor)


for i in range(int(input())):
	(l, r) = [int(x) for x in input().split()]
	sol = 0
	if r - l < 4:
		for i in range(l, r + 1):
			if i % 4 == 0:
				sol = sol ^ i
			elif i % 4 == 1:
				sol = sol ^ 1
			elif i % 4 == 2:
				sol = sol ^ i + 1
		print(sol)
		continue
	while l % 4 != 0:
		if l % 4 == 1:
			sol = sol ^ 1
		elif l % 4 == 2:
			sol = sol ^ l + 1
		if l == r:
			break
		l += 1
	while r % 4 != 3:
		if r % 4 == 0:
			sol = sol ^ r
		elif r % 4 == 1:
			sol = sol ^ 1
		elif r % 4 == 2:
			sol = sol ^ r + 1
		if l == r:
			break
		r -= 1
	if (r - l + 1) // 4 % 2 == 1:
		sol = sol ^ 2
	print(sol)


import sys

def A(i):
	return [i, 1, i + 1, 0][i % 4]

def solve(L, R):
	ans = 0
	k = 0
	for i in range(0, 4 - L % 4):
		k += 1
		ans ^= A(L + i)
	for i in range(0, (R + 1) % 4)[::-1]:
		k += 1
		ans ^= A(R - i)
	if (R + 1 - L - k) % 8 == 4:
		ans ^= 2
	return ans
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(solve(L, R))


import sys
import math

def map_known_cases(L, R):
	mod_L = L % 4
	mod_R = R % 4
	reps_even = math.floor((R - L) / 4) % 2 == 0
	if mod_L in [0, 3] and mod_R in [0, 1]:
		if reps_even:
			return R
		else:
			return R + 2
	elif mod_L == 0 and mod_R in [2, 3]:
		if reps_even:
			return 2
		else:
			return 0
	elif mod_L in [1, 2] and mod_R == 0:
		if reps_even:
			return (L ^ R) + 1
		else:
			return (L ^ R) - 1
	elif mod_L == 1 and mod_R == 1:
		if reps_even:
			return (L ^ R) + 1
		else:
			return (L ^ R) + 3
	elif mod_L in [1, 2] and mod_R in [2, 3]:
		if reps_even:
			return L + 1
		else:
			return L - 1
	elif mod_L == 2 and mod_R == 1:
		if reps_even:
			return (L ^ R) - 1
		else:
			return (L ^ R) - 3
	elif mod_L == 3 and mod_R == 2:
		if reps_even:
			return 2
		else:
			return 0
	elif mod_L == 3 and mod_R == 3:
		if reps_even:
			return 0
		else:
			return 2
	else:
		return None

def calculate_incremental(L, R):
	result = map_known_cases(L, R)
	print(result)
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	calculate_incremental(L, R)


print(*((lambda f, x, y: f(y) ^ f(x - 1))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 <= 7 else i if i % 8 <= 1 else i + 2, *map(int, input().split())) for _ in range(int(input()))), sep='\n')


def xoring(L):
	res = 0
	while L != []:
		res ^= L.pop()
	return res

def G(x):
	a = x % 8
	if a == 2 or a == 3:
		res = 2
	elif a == 6 or a == 7:
		res = 0
	elif a == 0 or a == 1:
		res = x
	else:
		res = x + 2
	return res
import sys
Q = int(input().strip())
for _ in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(G(L - 1) ^ G(R))


import sys

def get_value(n):
	if n % 4 == 0:
		return n
	elif n % 2 == 0:
		return n + 1
	elif n & 3 == 3:
		return 0
	else:
		return 1
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	if L == R:
		print(get_value(L))
		continue
	L2 = L
	while L2 % 4 != 0:
		L2 += 1
	R2 = R
	while (R2 + 1) % 4 != 0:
		R2 -= 1
	if L2 > R2:
		v = 0
		for i in range(L, R + 1):
			v = v ^ get_value(i)
		print(v)
		continue
	blocks = (R2 - L2 + 1) // 4
	if blocks % 2 == 0:
		v = 0
	else:
		v = 2
	for i in range(L, L2):
		v = v ^ get_value(i)
	for i in range(R2 + 1, R + 1):
		v = v ^ get_value(i)
	print(v)


import sys
import unittest

class XorSequence:

	def __init__(self, L=None, R=None):
		if L is None:
			(self.L, self.R) = map(int, input().strip().split(' '))
		else:
			self.L = L
			self.R = R

	def get_element_at_i(self, i):
		r = i % 4
		v = 0
		if r == 0:
			v = i
		elif r == 1:
			v = 1
		elif r == 2:
			v = i + 1
		elif r == 3:
			v = 0
		return v

	def range_calculae(self, left, right):
		txors = self.get_element_at_i(left)
		for i in range(left + 1, right + 1):
			txors ^= self.get_element_at_i(i)
		return txors

	def calculate(self):
		diff = int(self.R / 4) - int(self.L / 4)
		if diff >= 2:
			left_sum = self.range_calculae(self.L, (int(self.L / 4) + 1) * 4 - 1)
			mid_sum = 0
			if diff % 2 == 0:
				mid_sum = 2
			right_sum = self.range_calculae(int(self.R / 4) * 4, self.R)
			return left_sum ^ mid_sum ^ right_sum
		else:
			return self.range_calculae(self.L, self.R)

class TestXorSequence(unittest.TestCase):

	def test1(self):
		xors = XorSequence(2, 4)
		self.assertEquals(xors.calculate(), 7)

	def test2(self):
		xors = XorSequence(2, 8)
		self.assertEquals(xors.calculate(), 9)

	def test3(self):
		xors = XorSequence(5, 9)
		self.assertEquals(xors.calculate(), 15)
n = int(input().strip())
for i in range(n):
	xors = XorSequence()
	print(xors.calculate())


import sys

def Xor(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
	return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(Xor(R) ^ Xor(L - 1))


def x(a):
	return [a, 1, a + 1, 0][a % 4]
for i in range(int(input())):
	(l, r) = (int(i) for i in input().split())
	(a, a2) = (l // 4, r // 4)
	if a + 1 >= a2:
		s = 0
		for i in range(l, r + 1):
			s ^= x(i)
		print(s)
	else:
		d = a2 - a - 1
		s = 0
		for i in range(l, a * 4 + 4):
			s ^= x(i)
		for i in range(d & 1):
			s ^= 2
		for i in range(a2 * 4, r + 1):
			s ^= x(i)
		print(s)


def ansg(R):
	if R < 3:
		return R
	if R % 8 == 6 or R % 8 == 7:
		return 0
	if R % 8 == 0 or R % 8 == 1:
		return R
	if R % 8 == 4 or R % 8 == 5:
		return R + 2
	if R % 8 == 2 or R % 8 == 3:
		return 2
	return -1

def ansgg(L, R):
	return ansg(L - 1) ^ ansg(R)
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(ansgg(L, R))


import sys
print(*(lambda f: ((lambda x, y: f(y) ^ f(x - 1))(*map(int, input().split())) for _ in range(int(input()))))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 else i if i % 8 <= 1 else i + 2), sep='\n')


import sys

def xor_sum(l, r):
	result = 0
	patterns = [lambda x: x, lambda x: 1, lambda x: x + 1, lambda x: 0]
	i = l
	while i % 8 != 0 and i <= r:
		result ^= patterns[i % 4](i)
		i += 1
	if i < r - 7:
		i = r - r % 8
	while i <= r:
		result ^= patterns[i % 4](i)
		i += 1
	return result
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(xor_sum(L, R))


def get_val(x, l):
	val1 = None
	if x == 0 or x == 1:
		val1 = l
	elif x == 2 or x == 3:
		val1 = 2
	elif x == 4 or x == 5:
		val1 = l + 2
	elif x == 6 or x == 7:
		val1 = 0
	return val1

def gen_values(l, r):
	l = l - 1
	rem1 = l % 8
	rem2 = r % 8
	a = get_val(rem1, l)
	b = get_val(rem2, r)
	return a ^ b
q = int(input())
for i in range(q):
	l_r = input().strip().split(' ')
	(l, r) = [int(x) for x in l_r]
	ans = gen_values(l, r)
	print(ans)


def G(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
	return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(G(L - 1) ^ G(R))


def fun1(a):
	result = 0
	for i in range(a - a % 4, a + 1):
		result = result ^ i
	return result

def fun2(a):
	result = 0
	for i in range(a - a % 8, a + 1):
		result = result ^ fun1(i)
	return result
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = list(map(int, input().strip().split(' ')))
	print(fun2(L - 1) ^ fun2(R))


from math import ceil, floor
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	val = 0
	if R - L + 1 > 4:
		if L % 4 == 0:
			val ^= L ^ 1 ^ L + 3
			L += 3
		elif L % 4 == 1:
			val ^= 1 ^ L + 2
			L += 2
		elif L % 4 == 2:
			val ^= L + 1
			L += 1
		if R % 4 == 0:
			val ^= R
			R -= 1
		elif R % 4 == 1:
			val ^= 1 ^ R - 1
			R -= 2
		elif R % 4 == 2:
			val ^= R + 1 ^ 1 ^ R - 2
			R -= 3
		if (R - L) / 4 % 2 == 1:
			val ^= 2
	else:
		for i in range(L, R + 1):
			if i % 4 == 1:
				val ^= 1
			elif i % 4 == 2:
				val ^= i + 1
			elif i % 4 == 0:
				val ^= i
	print(val)


import sys

def g(x):
	t = x % 8
	if t == 0 or t == 1:
		return x
	elif t == 2 or t == 3:
		return 2
	elif t == 4 or t == 5:
		return x + 2
	else:
		return 0
q = int(input().strip())
for _ in range(q):
	(l, r) = map(int, input().strip().split(' '))
	print(g(r) ^ g(l - 1))


print(*(lambda f: ((lambda x, y: f(y) ^ f(x - 1))(*map(int, input().split())) for _ in range(int(input()))))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 else i if i % 8 <= 1 else i + 2), sep='\n')


import sys
Q = int(input().strip())

def G(x):
	a = int(x) % 8
	if a == 0 or a == 1:
		return int(x)
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return int(x) + 2
	if a == 6 or a == 7:
		return 0
	return 0
while Q > 0:
	(l, r) = input().strip().split(' ')
	print(G(int(r)) ^ G(int(l) - 1))
	Q = Q - 1


import sys

def f(x):
	r = x % 8
	if r in [0, 1]:
		return x
	if r in [2, 3]:
		return 2
	if r in [4, 5]:
		return x + 2
	if r in [6, 7]:
		return 0
Q = int(input().strip())
ls = [0]
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	res = 0
	res = f(L - 1) ^ f(R)
	print(res)


import sys

def A(n):
	if n % 4 == 0:
		return n
	elif n % 4 == 1:
		return 1
	elif n % 4 == 3:
		return 0
	else:
		return n + 1
Q = int(input())
for q in range(Q):
	(L, R) = [int(x) for x in input().split()]
	(l, q) = divmod(L, 4)
	(r, p) = divmod(R, 4)
	if r - l in {0, 1}:
		w = A(L)
		while L < R:
			L += 1
			w ^= A(L)
	else:
		w = 0
		while L % 4:
			w ^= A(L)
			L += 1
		while R % 4:
			w ^= A(R)
			R -= 1
		w ^= A(R)
		R -= 1
		if (R - L) // 4 % 2 == 0:
			w ^= 2
	print(w)


def A(x):
	if x % 4 == 0:
		return x
	elif x % 4 == 1:
		return 1
	elif x % 4 == 2:
		return x + 1
	elif x % 4 == 3:
		return 0
import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	value = 0
	while L % 8 != 0:
		value ^= A(L)
		L += 1
	tmp = R
	while tmp % 8 != 0:
		tmp -= 1
	while tmp <= R:
		value ^= A(tmp)
		tmp += 1
	print(value)


import sys

def G(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
	return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(G(R) ^ G(L - 1))


def ax(x):
	if x % 4 == 0:
		return x
	elif x % 4 == 1:
		return 1
	elif x % 4 == 2:
		return x + 1
	else:
		return 0

def fast_gx(x):
	m = x % 8
	if m == 0 or m == 1:
		return x
	if m == 2 or m == 3:
		return 2
	if m == 4 or m == 5:
		return x + 2
	if m == 6 or m == 7:
		return 0

def solve(l, r):
	return fast_gx(r) ^ fast_gx(l - 1)
q = int(input().strip())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(solve(l, r))


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	L = L - 1
	(r1, r2) = (0, 0)
	x1 = (L - 6) // 8 * 8 + 6 + 2
	if L < x1:
		r1 = 0
	elif L < x1 + 2:
		r1 = L
	elif L < x1 + 4:
		r1 = 2
	else:
		r1 = L + 2
	x2 = (R - 6) // 8 * 8 + 6 + 2
	if R < x2:
		r2 = 0
	elif R < x2 + 2:
		r2 = R
	elif R < x2 + 4:
		r2 = 2
	else:
		r2 = R + 2
	print(r1 ^ r2)


Q = int(input())
for q in range(Q):
	[L, R] = map(int, input().strip().split(' '))
	res = 0
	count = R - L + 1
	Ls = []
	if L % 4 == 3:
		count -= 1
	else:
		for l in range(L, L + 4):
			if l % 4 == 0:
				break
			count -= 1
			if l % 4 == 1:
				res ^= 1
			elif l % 4 == 2:
				res ^= l + 1
			Ls.append(l)
	Rs = []
	if R % 4 == 3:
		pass
	else:
		for r in range(R - R % 4, R + 1):
			if r % 4 == 3:
				break
			count -= 1
			if r % 4 == 0:
				res ^= r
			elif r % 4 == 1:
				res ^= 1
			elif r % 4 == 2:
				res ^= r + 1
			Rs.append(r)
	count /= 4
	if count % 2:
		res ^= 2
	print(res)


def red(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = map(int, input().strip().split())
	g = red(R) ^ red(L - 1)
	print(g)


print(*(lambda f: ((lambda x, y: f(y) ^ f(x - 1))(*map(int, input().split())) for _ in range(int(input()))))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 else i if i % 8 <= 1 else i + 2), sep='\n')


print(*(lambda f: ((lambda x, y: f(y) ^ f(x - 1))(*map(int, input().split())) for _ in range(int(input()))))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 else i if i % 8 <= 1 else i + 2), sep='\n')


for t in range(int(input())):
	(l, r) = map(int, input().split())
	if r - l > 4:
		(lx, ll) = (0, l - l % 4)
		ls = [ll, 1, ll + 3, 0]
		for i in range(l, ll + 4):
			lx ^= ls[i - ll]
		(rx, rl) = (0, r - r % 4)
		rs = [rl, 1, rl + 3, 0]
		for j in range(rl, r + 1):
			rx ^= rs[j - rl]
		x = 0
		if (rl - ll - 4) // 4 % 2 == 1:
			x = 2
		print(lx ^ rx ^ x)
	else:
		(x, xl) = (0, l - l % 4)
		xs = [xl, 1, xl + 3, 0, xl + 4, 1, xl + 7, 0]
		for k in range(l, r + 1):
			x ^= xs[k - xl]
		print(x)


from functools import reduce
from operator import xor

def compute_query(query):
	(l, r) = query
	(res, l) = (reduce(xor, range(l - l % 4, l + 1)), l + 2) if (r - l + 1) % 2 else (0, l + 1)
	l_end = l + 8 + l % 2 - l % 8
	res ^= reduce(xor, range(l, l_end, 2))
	r_start = r - r % 8 + l % 2
	res ^= reduce(xor, range(r_start, r + 1, 2))
	return res
n = int(input())
queries = [tuple(map(int, input().split())) for _ in range(n)]
print(*map(compute_query, queries), sep='\n')


import sys

def game(n):
	a = n % 8
	if a == 0 or a == 1:
		return n
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return n + 2
	if a == 6 or a == 7:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(game(R) ^ game(L - 1))


def f(n):
	if n == 0:
		return 0
	if n == 1:
		return 1
	n -= 2
	if n % 8 == 0 or n % 8 == 1:
		return 2
	if n % 8 == 4 or n % 8 == 5:
		return 0
	if n % 8 == 2 or n % 8 == 3:
		return n + 4
	if n % 8 == 6 or n % 8 == 7:
		return n + 2
	assert False
q = int(input())
for i in range(q):
	(l, r) = list(map(int, input().split()))
	print(f(r) ^ f(l - 1))


import sys

def G(k):
	a = k % 8
	if a == 0 or a == 1:
		return k
	elif a == 2 or a == 3:
		return 2
	elif a == 4 or a == 5:
		return k + 2
	else:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(G(L - 1) ^ G(R))


import sys
Q = int(input().strip())
for a0 in range(Q):
	(l, r) = [int(_) for _ in input().strip().split()]
	v = []
	if l & 3 == 1:
		v.append(1)
		v.append(l + 2)
		l += 2
	elif l & 3 == 2:
		v.append(l + 1)
		l += 1
	elif l & 3 == 0:
		l -= 1
	if r & 3 == 0:
		v.append(r)
		r -= 1
	elif r & 3 == 1:
		v.append(r - 1)
		v.append(1)
		r -= 2
	elif r & 3 == 2:
		r += 1
	s = (r - l >> 2 & 1) << 1
	for e in v:
		s ^= e
	print(s)


import sys
print(*(lambda f: ((lambda x, y: f(y) ^ f(x - 1))(*map(int, input().split())) for _ in range(int(input()))))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 else i if i % 8 <= 1 else i + 2), sep='\n')


import sys

def firstN(n):
	mod8 = n & 7
	if mod8 == 0 or mod8 == 1:
		return n
	elif mod8 == 2 or mod8 == 3:
		return 2
	elif mod8 == 4 or mod8 == 5:
		return n + 2
	else:
		return 0
nq = int(input().strip())
for _ in range(nq):
	(lft, rgt) = map(int, input().strip().split())
	print(firstN(lft - 1) ^ firstN(rgt))


def g(x):
	y = x % 8
	if y < 2:
		return x
	elif y < 4:
		return 2
	elif y < 6:
		return x + 2
	return 0
for _ in range(int(input())):
	(L, R) = [int(z) for z in input().split()]
	print(g(R) ^ g(L - 1))


import sys

def A(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(A(R) ^ A(L - 1))


print(*(lambda f: ((lambda x, y: f(y) ^ f(x - 1))(*map(int, input().split())) for _ in range(int(input()))))(lambda i: 2 if 2 <= i % 8 <= 3 else 0 if 6 <= i % 8 else i if i % 8 <= 1 else i + 2), sep='\n')


import sys

def get_acumulative_value(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	elif a == 2 or a == 3:
		return 2
	elif a == 4 or a == 5:
		return x + 2
	else:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	result = get_acumulative_value(R) ^ get_acumulative_value(L - 1)
	print(result)


import sys

def G(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
	return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	result = G(R) ^ G(L - 1)
	print(result)


def seq(n):
	return [n, 1, n + 1, 0][n % 4]
Q = int(input().strip())
for _ in range(Q):
	(L, R) = map(int, input().strip().split(' '))
	l = L - L % 4 + 4
	r = R - R % 4
	xor = 0
	if (r - l) // 4 % 2:
		xor = 2
	for x in range(L, l):
		xor ^= seq(x)
	for x in range(r, R + 1):
		xor ^= seq(x)
	print(xor)


import operator
import sys

def A(x):
	y = x % 4
	if y == 0:
		return x
	if y == 1:
		return 1
	if y == 2:
		return x + 1
	if y == 3:
		return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	ans = 0
	while L % 4 != 0:
		ans = ans ^ A(L)
		L += 1
	y = (R - L + 1) // 4
	if y % 2 == 0:
		ans = ans ^ 0
	else:
		ans = ans ^ 2
	x = L + y * 4
	while x <= R:
		ans = ans ^ A(x)
		x += 1
	print(ans)


def g(x):
	if x == 0:
		return 0
	n = x % 8
	if n < 2:
		return x
	if n < 4:
		return 2
	if n < 6:
		return 2 + x
	return 0
Q = int(input())
for q in range(Q):
	inp = [int(i) for i in input().split(' ')]
	(L, R) = (inp[0], inp[1])
	print(g(L - 1) ^ g(R))


from math import log

def cumulated_xor(n):
	if n <= 0:
		return 0
	else:
		r = 0
		if n % 4 == 1 or n % 4 == 2:
			r = 1
		for i in range(1, int(log(n, 2)) + 1):
			powi = 2 ** i
			if n % (powi * 2) >= powi and n % 2 == 0:
				r += powi
		return r

def cumulated_xor_step2(n):
	if n <= 0:
		return 0
	else:
		r = cumulated_xor(int(n / 2))
		r = r << 1
		mask = 2 ** (int(log(n, 2)) + 1) - 1
		r = r & mask
		r += n % 2 != 0 and (n + 1) % 4 != 0
		return r
T = int(input())
for t in range(T):
	(L, R) = map(int, input().split(' '))
	if (R - L + 1) % 2 == 0:
		print(cumulated_xor_step2(R) ^ cumulated_xor_step2(L - 1))
	else:
		print(cumulated_xor(L) ^ cumulated_xor_step2(R) ^ cumulated_xor_step2(L))


import sys
a = []

def extend(n):
	if n - len(a) <= 0:
		return
	else:
		if len(a) == 0:
			a.append(0)
		else:
			a.append(a[-1] ^ len(a))
		return extend(n)

def getXOR(l, r):
	return int(foo(r)) ^ int(foo(l - 1))

def foo(n):
	i = int(n % 8 / 2)
	if i == 0:
		return n
	elif i == 1:
		return 2
	elif i == 2:
		return n + 2
	else:
		return 0

def get(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	elif n == 2:
		return 3
	elif (n - 3) % 4 == 0:
		return 0
	elif (n - 3) % 4 == 1:
		return 4 + 4 * ((n - 4) / 4)
	elif (n - 3) % 4 == 2:
		return 1
	else:
		return 7 + 4 * ((n - 6) / 4)
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(getXOR(L, R))


import sys

def usePattern(n):
	rem = n % 8
	if rem == 6 or rem == 7:
		return 0
	elif rem == 3 or rem == 2:
		return 2
	elif rem == 4 or rem == 5:
		return n + 2
	elif rem == 1 or rem == 0:
		return n
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(usePattern(L - 1) ^ usePattern(R))


import sys

class XorSeq:

	def generate(self, x):
		m = x % 8
		if m == 0 or m == 1:
			return x
		if m == 2 or m == 3:
			return 2
		if m == 4 or m == 5:
			return x + 2
		if m == 6 or m == 7:
			return 0
		return 0

	def query(self, l, r):
		return self.generate(r) ^ self.generate(l - 1)
Q = int(input().strip())
xor = XorSeq()
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(xor.query(L, R))


import sys
X = lambda i: [i, 2, i + 2, 0][i % 8 // 2]
for _ in range(int(input())):
	(L, R) = map(int, input().strip().split())
	print(X(R) ^ X(L - 1))


import sys
from math import ceil, floor

def A(i):
	return [i, 1, i + 1, 0][i % 4]

def xorSeq(l, r):
	(r4, l4) = (floor(r / 4), ceil(l / 4))
	v = (r4 - l4 & 1) * 2
	for r in (range(l, 4 * l4), range(4 * r4, r + 1)):
		for i in r:
			v ^= A(i)
	return v
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	print(xorSeq(L, R))


import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	ans = 0
	for i in [R, L - 1]:
		r = i % 8
		if r == 0 or r == 1:
			state = i
		elif r == 2 or r == 3:
			state = 2
		elif r == 4 or r == 5:
			state = i + 2
		else:
			state = 0
		ans ^= state
	print(ans)


import sys
Q = int(input().strip())
for q in range(Q):
	(L, R) = map(int, input().strip().split())
	sl = (L + 1) // 8 * 8 - 1
	sr = (R + 1) // 8 * 8 - 1
	r = 0
	a = 0
	for i in range(sl + 1, L):
		a ^= i
		r ^= a
	a = 0
	for i in range(sr + 1, R + 1):
		a ^= i
		r ^= a
	print(r)


from functools import reduce
import sys
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	multiple = (R - L) // 16
	if multiple < 1:
		r = list(range(L, R + 1))
	else:
		rl = L + (4 - L % 4)
		r = list(range(L, rl))
		rr = list(range(rl + (multiple * 2 - 1) * 8, R + 1))
		r.extend(rr)
	values = []
	for num in r:
		if num % 4 == 0:
			values.append(num)
		elif num % 4 == 1:
			values.append(1)
		elif num % 4 == 2:
			values.append(num + 1)
	print(reduce(lambda x, y: x ^ y, values, 0))


from functools import reduce
import sys

def get_val(num):
	return num if num % 4 == 0 else num + 1 if num % 4 % 3 == 2 else num % 4 % 3

def go2zero(num, mod, top):
	xor_sum = 0
	while True:
		cont = get_val(num)
		if not cont or num > top:
			return (num, xor_sum)
		xor_sum ^= cont
		num += mod

def get_sum(l, r):
	(l, lsum) = go2zero(l, 1, r)
	(r, rsum) = go2zero(r, -1, r)
	if l > r:
		return lsum
	return (l - r) // 4 % 2 * 2 ^ lsum ^ rsum
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	ans = get_sum(L, R)
	print(ans)


import sys

def xorsum(a, l, r):
	s = a[l]
	for i in range(l + 1, r + 1):
		s = s ^ a[i]
	return s

def G(x):
	a = x % 8
	if a == 0 or a == 1:
		return x
	if a == 2 or a == 3:
		return 2
	if a == 4 or a == 5:
		return x + 2
	if a == 6 or a == 7:
		return 0
	return 0
Q = int(input().strip())
for a0 in range(Q):
	(L, R) = input().strip().split(' ')
	(L, R) = [int(L), int(R)]
	ans = G(R) ^ G(L - 1)
	print(ans)