Read problems statements in Mandarin Chinese and Russian as well. 

Vadim and Roman like discussing challenging problems with each other. One day Vadim told his friend following problem:
Given N points on a plane. Each point p is defined by it's two integer coordinates — p_{x} and p_{y}. The distance between points a and b is min(|a_{x} - b_{x}|, |a_{y} - b_{y}|). You should choose a starting point and make a route visiting every point exactly once, i.e. if we write down numbers of points in order you visit them we should obtain a permutation. Of course, overall distance walked should be as small as possible. The number of points may be up to 40.

"40? Maybe 20? Are you kidding?" – asked Roman. "No, it's not a joke" – replied Vadim. So Roman had nothing to do, but try to solve this problem. Since Roman is really weak in problem solving and you are the only friend, except Vadim, with whom Roman can discuss challenging tasks, he has nobody else to ask for help, but you!

------ Input ------ 

Input description.
The first line of the input contains an 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 denoting the number of points on a plane. The following N lines contain two space-separated integers each — coordinates of points. 
 
------ Output ------ 

Output description.
Output the answer for every test case in a separate line. The answer for every test case is a permutation of length N. In case there are several solutions that lead to minimal distance walked, you should choose the lexicographically smallest one. Let P denote such permutation. To make output smaller, you should output H(P). H(P) = P_{1} xor P_{2} xor ... xor P_{N}. Have a look at the example and it's explanation for better understanding. 
 
------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 40$
$0 ≤ absolute value of each coordinate ≤ 1000$
$1 ≤ sum over all N in a single test file ≤ 120$
 
----- Sample Input 1 ------ 
2
2
1 2
0 0
3
3 3
0 0
0 3
----- Sample Output 1 ------ 
3
0
----- explanation 1 ------ 
For the first test case permutation [1, 2] is optimal.  1 xor 2 = 3.

For the second one both [2, 3, 1] and [1, 3, 2] lead us to the shortest walk, but the second one is lexicographically smaller. So the answer is H([1, 3, 2]) = 1 xor 3 xor 2 = 0 .

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	arr = [0] * N
	for __ in range(N):
		arr[__] = tuple(map(int, input().split()))
	ans = 0
	for i in range(1, N + 1):
		ans ^= i
	print(ans)


t = int(input())
for tc in range(t):
	n = int(input())
	for i in range(n):
		(a, b) = map(int, input().split())
	k = 0
	for j in range(1, n + 1):
		k = k ^ j
	print(k)


for i in range(int(input())):
	a = int(input())
	l = []
	xor = 0
	for i in range(a):
		(a1, b1) = map(int, input().split())
		l.append([a1, b1])
	for i in range(1, a + 1):
		xor = xor ^ i
	print(xor)


t = int(input())
for ni in range(t):
	n = int(input())
	x = 0
	for i in range(1, n + 1):
		(a, b) = map(int, input().split())
		x = x ^ i
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	xy = []
	for _ in range(n):
		xy.append(list(map(int, input().split())))
	ans = 1
	for i in range(2, n + 1):
		ans ^= i
	print(ans)


import operator
for _ in range(int(input())):
	n = int(input())
	pts = []
	for i in range(n):
		pts.append(tuple(map(int, input().split())))
	y = 1
	for i in range(2, n + 1):
		y = y ^ i
	else:
		print(y)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		x = input()
		ans = ans ^ i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	for _ in range(n):
		(px, py) = map(int, input().split())
	px = 0
	for i in range(n + 1):
		px ^= i
	print(px)


for _ in range(int(input())):
	n = int(input())
	l = [list(map(int, input().split())) for i in range(n)]
	xoi = 0
	for i in range(1, n + 1):
		xoi ^= i
	print(xoi)


for _ in range(int(input())):
	n = int(input())
	P = []
	for _ in range(n):
		P.append(list(map(int, input().split())))
	xoroperator = 1
	for i in range(2, n + 1):
		xoroperator ^= i
	print(xoroperator)


t = int(input())
for i in range(t):
	s = int(input())
	p = []
	for j in range(s):
		(a, b) = map(int, input().split())
		p.append((a, b))
	r = 1
	for l in range(2, s + 1):
		r ^= l
	print(r)


for i in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		x = list(map(int, input().split()))
		ans = ans ^ i
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	for _ in range(n):
		(a, b) = map(int, input().split())
	ans = 0
	for j in range(1, n + 1):
		ans ^= j
	print(ans)


for t in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		(x, y) = map(int, input().split())
		ans = ans ^ i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = l1 = []
	s = 0
	for i in range(n):
		l.append(list(map(int, input().split())))
	for i in range(1, n + 1):
		s = s ^ i
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	xor = 0
	for j in range(n):
		(x, y) = map(int, input().split(' '))
	for k in range(1, n + 1):
		xor ^= k
	print(xor)


t = int(input())
for i in range(t):
	n = int(input())
	for i in range(n):
		(a, b) = map(int, input().split())
	ans = 1
	for i in range(2, n + 1):
		ans = ans ^ i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	points = []
	for _ in range(n):
		(x, y) = map(int, input().split())
		points.append((x, y))
	ans = 1
	for i in range(2, n + 1):
		ans ^= i
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	for _ in range(n):
		(a, b) = map(int, input().split())
	ans = 1
	for i in range(2, n + 1):
		ans ^= i
	print(ans)


import operator
for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		pts = input()
	y = 1
	for i in range(2, n + 1):
		y = y ^ i
	else:
		print(y)


for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		(a, b) = map(int, input().split())
		ans = ans ^ i
	print(ans)


n = int(input())
for i in range(n):
	s = int(input())
	m = 0
	for i in range(s):
		(x, y) = map(int, input().split())
	for i in range(1, s + 1):
		m ^= i
	print(m)


for _ in range(int(input())):
	n = int(input())
	a1 = 0
	for i in range(n):
		(a2, a3) = map(int, input().split())
		a1 = a1 ^ i + 1
	print(a1)


for _ in range(int(input())):
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
	k = 0
	for i in range(1, n + 1):
		k = k ^ i
	print(k)


t = int(input())
for tc in range(t):
	n = int(input())
	a = 0
	for j in range(1, n + 1):
		(c, d) = map(int, input().split())
		a ^= j
	print(a)


t = int(input())
while t > 0:
	n = int(input())
	l = list((map(int, input().split()) for i in range(n)))
	xori = 0
	for i in range(1, n + 1):
		xori ^= i
	print(xori)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = 0
	for j in range(n):
		listt = list(map(int, input().split()))
		a = a ^ j + 1
	print(a)


ujju = int(input())
for jyo in range(ujju):
	pspk = int(input())
	t = 0
	for r in range(1, pspk + 1):
		(hm, hs) = map(int, input().split())
		t = t ^ r
	print(t)


t = int(input())
for dummy in range(t):
	n = int(input())
	x = 0
	for i in range(n):
		(px, py) = map(int, input().split())
		x = x ^ i + 1
	print(x)


t = int(input())
for _ in range(t):
	N = int(input())
	for _ in range(N):
		(a, b) = map(int, input().split())
	k = 0
	for i in range(1, N + 1):
		k = k ^ i
	print(k)


t = int(input())
while t:
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		(a, b) = map(int, input().split())
		ans = ans ^ i
	print(ans)
	t -= 1


import operator
for _ in range(int(input())):
	n = int(input())
	pts = []
	for i in range(n):
		pts.append(tuple(map(int, input().split())))
	orig = list(zip(pts, range(1, n + 1)))
	rev = sorted(orig)
	y = 1
	for i in range(2, n + 1):
		y = y ^ i
	else:
		print(y)


for i in range(int(input())):
	a = int(input())
	l = 0
	for i in range(1, a + 1):
		(px, pu) = map(int, input().split())
		l = l ^ i
	print(l)


import numpy as np
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append([int(c) for c in input().split()])
	p = a.copy()
	mi = 9999
	x = 1
	(start, temp) = (a[0], [])
	a.remove(a[0])
	for _ in range(n - 1):
		l = len(a)
		for i in range(l):
			if min(abs(start[0] - a[i][0]), abs(start[1] - a[i][1])) < mi:
				mi = min(abs(start[0] - a[i][0]), abs(start[1] - a[i][1]))
				temp = a[i]
		start = temp
		x = np.bitwise_xor(x, p.index(start) + 1)
		a.remove(a[a.index(start)])
		mi = 9999
	print(x)


tests = int(input())
for i in range(tests):
	n = int(input())
	ans = 0
	for x in range(n):
		(z, y) = map(int, input().split())
		ans ^= x
	print(ans ^ n)