Chef loves bitwise operations. So, he creates the following problem but needs your help to solve it.

Chef calls a sequence of integers A_{1}, A_{2}, \ldots, A_{N} tasty if it satisfies the following condition:
parity(A_{i} \& A_{i+1}) \neq parity(A_{i} | A_{i+1}) for 1 ≤ i < N.

Chef gives you a sequence A_{1}, A_{2}, \ldots, A_{N}. You may perform the following operation on the sequence any number of times (possibly 0): 
Choose 2 indices i and j (1 ≤ i, j ≤ n ; i \neq j) and change A_{i} to A_{i} \oplus A_{j}.

Chef is asking you to make the sequence tasty using the minimum number of operations, or report that it is impossible.

As a friendly reminder,
parity(x) denotes the remainder of dividing x by 2
\&  denotes the [bitwise AND operation]
|  denotes the [bitwise OR operation]
\oplus  denotes the [bitwise XOR operation].

------ Input Format ------ 

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

For each test case:
- If it is impossible to convert the given sequence into a tasty sequence using the given operations, print a single line containing the integer -1.
- Otherwise, first, print a line containing a single integer M ― the minimum number of operations you have to perform.
- Then, print M lines describing these operations in the order in which you want to perform them. For each k (1 ≤ k ≤ M), the k-th of these lines should contain two space-separated integers i and j (1 ≤ i, j ≤ n ; i \neq j) ― the indices on which the k-th operation is performed.

If there are multiple solutions, you may find any one of them.

------ Constraints ------ 

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

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
2
2
0 0
3
6 16 69
----- Sample Output 1 ------ 
-1
1
1 3
----- explanation 1 ------ 
Test case $1$: It is impossible to make $A$ tasty using the given operations.

Test case $2$: We can choose $i=1$ and $j=3$ and apply the operation which converts $A$ into $[\textcolor{blue}{67},16,\textcolor{blue}{69}]$ which is tasty.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Complete search

Constructive algorithms

Ad-hoc


Solutions:
def find_k(a):
	e = 0
	i = 0
	o = 0
	d = 0
	for m in range(len(a)):
		if a[m] % 2 != 0:
			d += 1
			break
		else:
			continue
	while True:
		if 2 * i >= len(a):
			break
		if a[2 * i] % 2 != 0:
			e += 1
		if a[2 * i] % 2 == 0:
			o += 1
		if 2 * i + 1 >= len(a):
			break
		if a[2 * i + 1] % 2 == 0:
			e += 1
		if a[2 * i + 1] % 2 != 0:
			o += 1
		i += 1
	return (e, o, d)
T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	i = 0
	(e, o, d) = find_k(a)
	if d == 0:
		print(-1)
	else:
		print(min(e, o))
	while True:
		if d == 0 or min(e, o) == 0:
			break
		if min(e, o) == e:
			if 2 * i >= len(a):
				break
			if a[2 * i] % 2 != 0:
				for j in range(len(a)):
					if a[j] % 2 != 0 and 2 * i != j:
						a[2 * i] = a[2 * i] ^ a[j]
						print(2 * i + 1, j + 1)
						break
					else:
						continue
			if 2 * i + 1 >= len(a):
				break
			if a[2 * i + 1] % 2 == 0:
				for j in range(len(a)):
					if a[j] % 2 != 0:
						a[2 * i + 1] = a[2 * i + 1] ^ a[j]
						print(2 * i + 1 + 1, j + 1)
						break
					else:
						continue
		else:
			if 2 * i >= len(a):
				break
			if a[2 * i] % 2 == 0:
				for j in range(len(a)):
					if a[j] % 2 != 0:
						a[2 * i] = a[2 * i] ^ a[j]
						print(2 * i + 1, j + 1)
						break
					else:
						continue
			if 2 * i + 1 >= len(a):
				break
			if a[2 * i + 1] % 2 != 0:
				for j in range(len(a)):
					if a[j] % 2 != 0 and 2 * i + 1 != j:
						a[2 * i + 1] = a[2 * i + 1] ^ a[j]
						print(2 * i + 2, j + 1)
						break
					else:
						continue
		i += 1


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	count = 0
	nodd = 0
	neven = 0
	for i in range(n):
		if l[i] % 2 == 0:
			neven = neven + 1
		else:
			nodd = nodd + 1
	if nodd == 0:
		print(-1)
	else:
		if neven >= nodd:
			oddindex = 0
			evenindex = 0
			for i in range(n):
				if l[i] % 2 == 0:
					if i % 2 == 0:
						evenindex += 1
					else:
						oddindex += 1
			if oddindex >= evenindex:
				for i in range(n):
					if l[i] % 2 == 1 and i % 2 == 0:
						firstcrtodd = i
						break
				i = 0
				while i < n:
					if l[i] % 2 == 0:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
				i = 1
				while i < n:
					if l[i] % 2 == 1:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
			else:
				for i in range(n):
					if l[i] % 2 == 1 and i % 2 == 1:
						firstcrtodd = i
						break
				i = 1
				while i < n:
					if l[i] % 2 == 0:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
				i = 0
				while i < n:
					if l[i] % 2 == 1:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
		else:
			oddindex = 0
			evenindex = 0
			for i in range(n):
				if l[i] % 2 == 1:
					if i % 2 == 0:
						evenindex += 1
					else:
						oddindex += 1
			if oddindex >= evenindex:
				for i in range(n):
					if l[i] % 2 == 1 and i % 2 == 1:
						firstcrtodd = i
						break
				i = 0
				while i < n:
					if l[i] % 2 == 1:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
				i = 1
				while i < n:
					if l[i] % 2 == 0:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
			else:
				for i in range(n):
					if l[i] % 2 == 1 and i % 2 == 0:
						firstcrtodd = i
						break
				i = 0
				while i < n:
					if l[i] % 2 == 0:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
				i = 1
				while i < n:
					if l[i] % 2 == 1:
						l[i] = l[i] ^ l[firstcrtodd]
						ans.append(str(i + 1) + ' ' + str(firstcrtodd + 1))
						count = count + 1
					i = i + 2
		print(count)
		for i in ans:
			print(i)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list((i % 2 for i in map(int, input().split())))
	if a.count(1) == 0:
		print(-1)
	else:
		(l0, l1) = (-1, -1)
		for i in range(n):
			if a[i] % 2:
				if i % 2:
					l1 = i
				else:
					l0 = i
		Answ121 = []
		if l0 != -1:
			for i in range(n):
				if i % 2 == a[i] % 2:
					Answ121.append([i + 1, l0 + 1])
		Answ122 = []
		if l1 != -1:
			for i in range(n):
				if i % 2 != a[i] % 2:
					Answ122.append([i + 1, l1 + 1])
		if l0 == -1:
			print(len(Answ122))
			for i in Answ122:
				print(*i)
		elif l1 == -1:
			print(len(Answ121))
			for i in Answ121:
				print(*i)
		else:
			print(min(len(Answ121), len(Answ122)))
			if len(Answ121) < len(Answ122):
				for i in Answ121:
					print(*i)
			else:
				for i in Answ122:
					print(*i)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	count0 = 0
	count1 = 0
	a0 = []
	a1 = []
	ans = 0
	for i in range(n):
		if i % 2 == 0 and a[i] % 2 == 1:
			x = i
			count0 = count0 + 1
		if i % 2 == 1 and a[i] % 2 == 1:
			y = i
			count1 = count1 + 1
	if count0 > count1:
		for i in range(n):
			if i % 2 == 1 and a[i] % 2 == 1 or (i % 2 == 0 and a[i] % 2 == 0):
				ans = ans + 1
				a0.append(i)
		print(ans)
		for i in range(len(a0)):
			print(a0[i] + 1, x + 1)
	elif count0 == 0 and count1 == 0:
		print('-1')
	else:
		for i in range(n):
			if i % 2 == 0 and a[i] % 2 == 1 or (i % 2 == 1 and a[i] % 2 == 0):
				ans = ans + 1
				a1.append(i)
		print(ans)
		for i in range(len(a1)):
			print(a1[i] + 1, y + 1)


for t in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	num = A
	for i in range(n):
		num[i] %= 2
	if 1 in num:
		eve = odd = 0
		for i in range(n):
			if num[i] == i % 2:
				eve += 1
			else:
				odd += 1
		temp = []
		if eve > odd:
			for i in range(n):
				temp.append(i % 2)
		else:
			for i in range(n):
				temp.append((i + 1) % 2)
		one = 0
		flag = 0
		for i in range(n):
			if num[i] == 1 and temp[i] == 1:
				one = i
				flag = 1
				break
		if flag != 1:
			for i in range(n):
				if temp[i] == 1:
					temp[i] = 0
				else:
					temp[i] = 1
			for i in range(n):
				if nos[i] == 1 and temp[i] == 1:
					one = i
					break
		m = 0
		out = []
		for i in range(n):
			if temp[i] != num[i]:
				m += 1
				if num[i] == 0:
					out.append([i + 1, one + 1])
				else:
					out.append([i + 1, one + 1])
		print(m)
		for i in out:
			print(i[0], i[1], sep=' ')
	else:
		print(-1)


def printi(ans):
	print(len(ans))
	for i in ans:
		print(i[0] + 1, i[1] + 1)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = [0] * len(arr)
	odd = []
	flag = 0
	for i in range(len(arr)):
		l[i] = arr[i] % 2
		if arr[i] % 2 == 1:
			odd.append(i)
	if odd == []:
		print(-1)
		continue
	(ans, ans1) = ([], [])
	if l[0] % 2 != 1:
		l[0] = 1
		ans.append([0, odd[-1]])
	for i in range(1, len(l)):
		if i % 2 == 0 and l[i] == 0:
			ans.append([i, 0])
		elif i % 2 == 1 and l[i] == 1:
			ans.append([i, 0])
	l[0] = arr[0] % 2
	if l[1] % 2 != 1:
		l[1] = 1
		ans1.append([1, odd[-1]])
	for i in range(len(l)):
		if i != 1:
			if i % 2 == 0 and l[i] == 1:
				ans1.append([i, 1])
			elif i % 2 == 1 and l[i] == 0:
				ans1.append([i, 1])
	if len(ans) < len(ans1):
		printi(ans)
	else:
		printi(ans1)


for _ in range(int(input())):
	l = int(input())
	seq = [int(i) % 2 for i in input().split()]
	if not any(seq):
		print(-1)
	else:
		count = [[], []]
		k = 0
		for i in range(l):
			count[k % 2].append(i)
			if i < l - 1 and seq[i] == seq[i + 1]:
				k += 1
		min = count[0] if len(count[0]) <= len(count[1]) else count[1]
		print(len(min))
		for i in min:
			seq[i] = -1
			print(i + 1, 1 + seq.index(1))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	if [ele % 2 for ele in a].count(1) == 0:
		print(-1)
		continue
	x = delta = 0
	for i in range(n):
		if a[i] % 2 != i % 2:
			x += 1
	if x > n - x:
		delta += 1
	ind = -1
	for i in range(n):
		if a[i] % 2 and (i + delta) % 2:
			ind = i
			break
	assert ind != -1
	ops = []
	for i in range(n):
		if a[i] % 2 != (i + delta) % 2:
			ops.append((i + 1, ind + 1))
	print(len(ops))
	assert len(ops) == min(x, n - x)
	for i in ops:
		a[i[0] - 1] ^= a[i[1] - 1]
		print(*i)
	for i in range(n - 1):
		assert a[i] % 2 != a[i + 1] % 2


for _ in range(int(input())):
	n = int(input())
	a = [int(x) % 2 for x in input().split()]
	target1 = [x % 2 for x in range(n)]
	target2 = [(x + 1) % 2 for x in range(n)]
	chk1 = chk2 = 0
	changeind = -1
	for i in range(n):
		if a[i] != target1[i]:
			chk1 += 1
		elif a[i] != target2[i]:
			chk2 += 1
		else:
			pass
	if chk1 < chk2:
		target = target1
		chk = chk1
	else:
		target = target2
		chk = chk2
	for i in range(n):
		if a[i] == 1 and target[i] == 1:
			changeind = i
			break
	if changeind == -1:
		print(-1)
	else:
		resinds = []
		for i in range(n):
			if a[i] != target[i] and i != changeind:
				resinds.append(i)
		print(chk)
		for i in range(len(resinds)):
			print(resinds[i] + 1, changeind + 1)


def solver(n, arr):

	def utility(arr):
		indices = [[], []]
		for i in range(n):
			if parity[i] == arr[i]:
				indices[parity[i]].append(i)
		altered = []
		for i in range(n):
			if parity[i] != arr[i]:
				search_val = 1
				found_index = -1
				for j in indices[search_val]:
					if j != i:
						found_index = j
						break
				if found_index == -1:
					return None
				altered.append((i, found_index))
				parity[i] = search_val
		return altered
	parity = [i % 2 for i in arr]
	s1 = [i % 2 for i in range(n)]
	s2 = [(i + 1) % 2 for i in range(n)]
	score1 = score2 = 0
	for i in range(n):
		if parity[i] == s1[i]:
			score1 += 1
		else:
			score2 += 1
	if score1 > score2:
		c1 = utility(s1)
		c2 = None
	elif score2 > score1:
		c2 = utility(s2)
		c1 = None
	else:
		c1 = utility(s1)
		parity = [i % 2 for i in arr]
		c2 = utility(s2)
	if c1 is None and c2 is None:
		print('-1')
	else:
		if c1 is None:
			changes = c2
		elif c2 is None:
			changes = c1
		elif len(c1) <= len(c2):
			changes = c1
		else:
			changes = c2
		print(len(changes))
		for tup in changes:
			print(f'{tup[0] + 1} {tup[1] + 1}')
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split(' ')))
	solver(n, arr)


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	n = int(input())
	l = input().split()
	li = [int(i) % 2 for i in l]
	ind = -1
	z = 0
	ans = 10 ** 12
	for i in range(n):
		if li[i]:
			ind = i
			break
	if ind == -1:
		print(-1)
		continue
	c1 = 0
	for i in range(n):
		if li[i] != i % 2:
			c1 += 1
	c2 = 0
	for i in range(n):
		if li[i] != (i + 1) % 2:
			c2 += 1
	if c1 < c2:
		print(c1)
		for i in range(n):
			if li[i] != i % 2:
				if i == ind:
					continue
				print(i + 1, ind + 1)
		if li[ind] != ind % 2:
			for i in range(n):
				if i != ind and i % 2:
					print(ind + 1, i + 1)
					break
	else:
		print(c2)
		for i in range(n):
			if li[i] != (i + 1) % 2:
				if i == ind:
					continue
				print(i + 1, ind + 1)
		if li[ind] != (ind + 1) % 2:
			for i in range(n):
				if i != ind and (i + 1) % 2:
					print(ind + 1, i + 1)
					break


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	e = o = ans = 0
	for j in range(n):
		if a[j] % 2 == 0:
			ans += 1
	if ans == n:
		print(-1)
	else:
		for i in range(n):
			if i % 2 != 0 and a[i] % 2 != 0:
				b = i
			if i % 2 == 0 and a[i] % 2 != 0:
				c = i
			if i % 2 == 0 and a[i] % 2 == 0 or (i % 2 != 0 and a[i] % 2 != 0):
				e += 1
			elif i % 2 == 0 and a[i] % 2 != 0 or (i % 2 != 0 and a[i] % 2 == 0):
				o += 1
		if o <= e:
			print(n - e)
			for x in range(n):
				if x % 2 == 0:
					if a[x] % 2 != 0:
						print(x + 1, b + 1)
				elif a[x] % 2 == 0:
					print(x + 1, b + 1)
		else:
			print(n - o)
			for y in range(n):
				if y % 2 == 0:
					if a[y] % 2 == 0:
						print(y + 1, c + 1)
				elif a[y] % 2 != 0:
					print(y + 1, c + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	eo = 0
	oe = 0
	ans = 0
	for j in range(n):
		if a[j] % 2 == 0:
			ans += 1
	if ans == n:
		print(-1)
	else:
		for i in range(n):
			if i % 2 != 0 and a[i] % 2 != 0:
				b = i
			if i % 2 == 0 and a[i] % 2 != 0:
				c = i
			if i % 2 == 0 and a[i] % 2 == 0 or (i % 2 != 0 and a[i] % 2 != 0):
				eo += 1
			elif i % 2 == 0 and a[i] % 2 != 0 or (i % 2 != 0 and a[i] % 2 == 0):
				oe += 1
		if oe <= eo:
			print(n - eo)
			for x in range(n):
				if x % 2 == 0:
					if a[x] % 2 != 0:
						print(x + 1, b + 1)
				elif a[x] % 2 == 0:
					print(x + 1, b + 1)
		else:
			print(n - oe)
			for y in range(n):
				if y % 2 == 0:
					if a[y] % 2 == 0:
						print(y + 1, c + 1)
				elif a[y] % 2 != 0:
					print(y + 1, c + 1)


T = int(input())
for _ in range(T):
	N = int(input())
	A = input().split(' ')
	oePatternXor = []
	eoPatternXor = []
	eoPivot = -1
	oePivot = -1
	for (i, n) in enumerate(A):
		V = int(n) % 2
		if i % 2 == 0 and V == 0 or (i % 2 == 1 and V == 1):
			eoPatternXor.append(i + 1)
			if oePivot == -1 and V == 1:
				oePivot = i + 1
		elif i % 2 == 1 and V == 0 or (i % 2 == 0 and V == 1):
			oePatternXor.append(i + 1)
			if eoPivot == -1 and V == 1:
				eoPivot = i + 1
	if eoPivot == -1 and oePivot == -1:
		print(-1)
	else:
		if eoPivot != -1 and oePivot != -1:
			if oePivot != -1 and len(oePatternXor) <= len(eoPatternXor):
				(res, pivot) = (oePatternXor, oePivot)
			else:
				(res, pivot) = (eoPatternXor, eoPivot)
		elif eoPivot != -1:
			(res, pivot) = (eoPatternXor, eoPivot)
		elif oePivot != -1:
			(res, pivot) = (oePatternXor, oePivot)
		print(len(res))
		for v in res:
			print(v, pivot)


try:
	t = int(float(input()))
	for _ in range(t):
		n = int(float(input()))
		a = list(map(int, input().split()))
		b = [i % 2 for i in a]
		if not any(b):
			print(-1)
		else:
			(oe, eo) = (0, 0)
			(o1, o2) = (0, 0)
			for i in range(n):
				if i % 2 == 0 and b[i] == 1:
					eo += 1
				elif i % 2 == 1 and b[i] == 0:
					eo += 1
				if i % 2 == 1 and b[i] == 1:
					o1 = i
			for i in range(n):
				if i % 2 == 0 and b[i] == 0:
					oe += 1
				elif i % 2 == 1 and b[i] == 1:
					oe += 1
				if i % 2 == 0 and b[i] == 1:
					o2 = i
			if eo <= oe:
				print(eo)
				for i in range(n):
					if i % 2 == 0 and b[i] == 1:
						print(i + 1, o1 + 1)
					elif i % 2 == 1 and b[i] == 0:
						print(i + 1, o1 + 1)
			else:
				print(oe)
				for i in range(n):
					if i % 2 == 0 and b[i] == 0:
						print(i + 1, o2 + 1)
					elif i % 2 == 1 and b[i] == 1:
						print(i + 1, o2 + 1)
except:
	pass


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if a[i] % 2 == 1:
			count += 1
	if count == 0:
		print(-1)
	else:
		ans1 = []
		ans2 = []
		oddpos = -1
		evenpos = -1
		ele1 = 0
		ele2 = 0
		for i in range(n):
			if a[i] % 2 == 1 and i % 2 == 1:
				oddpos = i
				ele1 = a[i]
			if a[i] % 2 == 1 and i % 2 == 0:
				evenpos = i
				ele2 = a[i]
		if oddpos >= 0:
			for i in range(n):
				if a[i] & 1 == 1 and i & 1 == 0:
					ans1.append((i + 1, oddpos + 1))
				if a[i] & 1 == 0 and i & 1 == 1:
					ans1.append((i + 1, oddpos + 1))
		if evenpos >= 0:
			for i in range(n):
				if a[i] & 1 == 1 and i & 1 == 1:
					ans2.append((i + 1, evenpos + 1))
				if a[i] & 1 == 0 and i & 1 == 0:
					ans2.append((i + 1, evenpos + 1))
		ans1len = len(ans1)
		ans2len = len(ans2)
		if ans2len == 0:
			print(ans1len)
			for i in ans1:
				print(i[0], i[1])
		elif ans1len == 0:
			print(ans2len)
			for i in ans2:
				print(i[0], i[1])
		elif len(ans1) < len(ans2):
			print(ans1len)
			for i in ans1:
				print(i[0], i[1])
		else:
			print(ans2len)
			for i in ans2:
				print(i[0], i[1])
	t = t - 1


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	if all([i & 1 == 0 for i in l]):
		print('-1')
		continue
	l1 = []
	l2 = []
	l3 = []
	odd_index = 0
	for i in range(n):
		if i & 1 == 0:
			if l[i] & 1 == 0:
				l2.append(i)
			else:
				l1.append(i)
		elif l[i] & 1 == 0:
			l1.append(i)
		else:
			l2.append(i)
	op_req = min(len(l1), len(l2))
	if len(l1) > len(l2):
		l3 = l2
	else:
		l3 = l1
	for i in range(len(l)):
		if l[i] & 1 == 1 and i not in l3:
			odd_index = i
			break
		else:
			continue
	print(op_req)
	for i in l3:
		print(i + 1, odd_index + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(evenI, oddI) = (0, 0)
	(even, odd, oddP) = (False, False, False)
	(kE, kO) = (0, 0)
	(wE, wO) = ([], [])
	for i in range(n):
		if a[i] % 2 != 0:
			oddP = True
			if i % 2 == 0:
				evenI = i
				even = True
			else:
				oddI = i
				odd = True
	if not oddP:
		print('-1')
	else:
		if even:
			for i in range(n):
				if i % 2 == 0 and a[i] % 2 == 0:
					kE += 1
					wE.append(i + 1)
				if i % 2 != 0 and a[i] % 2 != 0:
					kE += 1
					wE.append(i + 1)
		if odd:
			for i in range(n):
				if i % 2 == 0 and a[i] % 2 != 0:
					kO += 1
					wO.append(i + 1)
				if i % 2 != 0 and a[i] % 2 == 0:
					kO += 1
					wO.append(i + 1)
		if kE > kO:
			if kO > 0:
				print(kO)
				for i in range(kO):
					print(wO[i], oddI + 1, end=' ')
			else:
				print(kE)
				for i in range(kE):
					print(wE[i], evenI + 1, end=' ')
		elif kE <= kO:
			if kE > 0:
				print(kE)
				for i in range(kE):
					print(wE[i], evenI + 1, end=' ')
			else:
				print(kO)
				for i in range(kO):
					print(wO[i], oddI + 1, end=' ')


from sys import stdin, stdout
inp_num = lambda : int(input())
inp_lis = lambda : list(map(int, input().split()))
for _ in range(inp_num()):
	n = inp_num()
	l1 = inp_lis()
	l = []
	re = []
	re1 = []
	a = 0
	cou1 = -1
	for i in l1:
		if i % 2 == 0:
			l.append(0)
		else:
			l.append(1)
			cou1 = a
		if a % 2 == 0:
			re.append(1)
			re1.append(0)
		else:
			re.append(0)
			re1.append(1)
		a += 1
	if cou1 == -1:
		print(-1)
		continue
	an1 = 0
	an2 = 0
	for i in range(n):
		if l[i] == re[i]:
			an2 += 1
		else:
			an1 += 1
	print(min(an1, an2))
	if an2 >= an1:
		for i in range(n):
			if l[i] == re[i]:
				continue
			elif i == 0 and l[0] == 0:
				print(i + 1, cou1 + 1, sep=' ')
			elif i == 1 and l[i] == 1:
				print(2, 1, sep=' ')
			elif l[i] != re[i]:
				if l[i] == 1:
					print(i + 1, 1, sep=' ')
				else:
					print(i + 1, 1, sep=' ')
	else:
		for i in range(n):
			if l[i] == re1[i]:
				continue
			elif i == 0 and l[i] == 1 and (l[1] == 1):
				print(1, 2, sep=' ')
			elif i == 0 and l[i] == 1 and (l[1] == 0):
				print(2, 1, sep=' ')
				l[1] = 1
				print(1, 2, sep=' ')
			elif i == 1:
				print(2, cou1 + 1, sep=' ')
			elif l[i] != re1[i]:
				if l[i] == 1:
					print(i + 1, 2, sep=' ')
				else:
					print(i + 1, 2, sep=' ')


p1 = [0, 1]
p2 = [1, 0]

def parity(x):
	return x & 1
for t in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().strip().split()))
	idx = 0
	c1 = 0
	c2 = 0
	sol_exists = False
	s1 = []
	s2 = []
	o1 = -1
	o2 = -1
	for i in range(n):
		p = parity(a[i])
		if p != p1[idx]:
			s1.append(i + 1)
			c1 += 1
		elif p == 1:
			o1 = i + 1
		if p != p2[idx]:
			s2.append(i + 1)
			c2 += 1
		elif p == 1:
			o2 = i + 1
		idx = (idx + 1) % 2
	if o1 == -1 and o2 == -1:
		print(-1)
		continue
	m = min(c1, c2)
	print(m)
	if c1 <= c2:
		for i in s1:
			print(i, o1)
	else:
		for i in s2:
			print(i, o2)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().strip().split()))
	arr_odd = []
	arr_even = []
	even = 0
	for i in range(len(lst)):
		lst[i] = lst[i] % 2
		if lst[i] == 0:
			even += 1
		arr_even.append(i % 2)
		arr_odd.append((i + 1) % 2)
	if even == len(lst):
		print(-1)
		continue
	chose_arr = []
	count_even = 0
	count_odd = 0
	for i in range(len(lst)):
		if lst[i] == arr_even[i]:
			count_even += 1
		if lst[i] == arr_odd[i]:
			count_odd += 1
	if count_even >= count_odd:
		chose_arr = arr_even
	else:
		chose_arr = arr_odd
	result = []
	j = len(lst) - 1
	while j >= 0:
		if lst[j] == 1:
			break
		j -= 1
	odd_index = 0
	res = 0
	for i in range(2):
		if lst[i] != chose_arr[i]:
			res += 1
			lst[i] = chose_arr[i]
			result.append([i + 1, j + 1])
	for i in range(len(lst)):
		if lst[i] % 2 != 0:
			odd_index = i
			break
	for i in range(2, len(lst)):
		if lst[i] != chose_arr[i]:
			res += 1
			result.append([i + 1, odd_index + 1])
	print(res)
	for i in range(res):
		print(result[i][0], result[i][1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(valid, odd, even) = (False, False, False)
	(odd_pos, even_pos) = (-1, -1)
	for i in range(n):
		if a[i] % 2:
			valid = True
			if i % 2:
				odd = True
				odd_pos = i
			else:
				even = True
				even_pos = i
	if valid == False:
		print(-1)
		continue
	r_odd = []
	r_even = []
	ops_odd = 0
	ops_even = 0
	if odd:
		for i in range(n):
			if i % 2:
				if a[i] % 2 == 0:
					ops_odd += 1
					r_odd.append([i + 1, odd_pos + 1])
			elif a[i] % 2 != 0:
				ops_odd += 1
				r_odd.append([i + 1, odd_pos + 1])
	if even:
		for i in range(n):
			if i % 2:
				if a[i] % 2 != 0:
					ops_even += 1
					r_even.append([i + 1, even_pos + 1])
			elif a[i] % 2 == 0:
				ops_even += 1
				r_even.append([i + 1, even_pos + 1])
	if odd and even:
		if ops_even <= ops_odd:
			print(ops_even)
			for i in r_even:
				print(i[0], i[1])
		else:
			print(ops_odd)
			for i in r_odd:
				print(i[0], i[1])
	elif odd:
		print(ops_odd)
		for i in r_odd:
			print(i[0], i[1])
	else:
		print(ops_even)
		for i in r_even:
			print(i[0], i[1])


t = int(input())
while t:
	n = int(input())
	ls = list(map(int, input().split(' ')))
	(lastOddPos, evenPos, oddPos) = (-1, 0, 0)
	if [ele % 2 for ele in ls].count(1) == 0:
		print(-1)
		t -= 1
		continue
	for i in range(1, n + 1):
		if i % 2:
			if ls[i - 1] % 2:
				evenPos += 1
			else:
				oddPos += 1
		elif ls[i - 1] % 2:
			oddPos += 1
		else:
			evenPos += 1
		if ls[i - 1] % 2:
			lastOddPos = i
	if oddPos < evenPos:
		print(oddPos)
		for i in range(1, n + 1):
			if i % 2:
				if ls[i - 1] % 2 == 0:
					print(i, lastOddPos)
			elif ls[i - 1] % 2 == 1:
				print(i, lastOddPos)
			if i == 1:
				lastOddPos = 1
	else:
		print(evenPos)
		for i in range(1, n + 1):
			if i % 2:
				if ls[i - 1] % 2 == 1:
					print(i, lastOddPos)
			elif ls[i - 1] % 2 == 0:
				print(i, lastOddPos)
			if i == 2:
				lastOddPos = 2
	t -= 1


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = []
	arr2 = []
	t = ans = x = odd = 0
	for i in range(n):
		if arr[i] % 2:
			odd += 1
	if odd:
		for i in range(n):
			if arr[i] % 2 != t:
				arr1.append(i)
				ans += 1
			if arr[i] % 2 and i % 2:
				x = i
			if t == 0:
				t = 1
			else:
				t = 0
		(t, ans1, x1) = (1, 0, 0)
		for i in range(n):
			if arr[i] % 2 != t:
				arr2.append(i)
				ans1 += 1
			if arr[i] % 2 and i % 2 == 0:
				x1 = i
			if t == 0:
				t = 1
			else:
				t = 0
		if ans1 > ans:
			print(ans)
			for i in range(ans):
				print(f'{arr1[i] + 1} {x + 1}')
		else:
			print(ans1)
			for i in range(ans1):
				print(f'{arr2[i] + 1} {x1 + 1}')
	else:
		print(-1)
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = []
	b = []
	c = []
	d = []
	count = 0
	for i in range(n):
		if i % 2 == 0:
			if arr[i] % 2 == 0:
				d.append(i)
				count += 1
			else:
				c.append(i)
		elif arr[i] % 2 == 0:
			b.append(i)
			count += 1
		else:
			a.append(i)
	if count == n:
		print(-1)
		continue
	x = len(b)
	y = len(c)
	z = x + y
	m = len(a)
	n = len(d)
	o = m + n
	if z < o:
		print(z)
		if m != 0:
			ans = a[0]
		else:
			ans = c[0]
		for i in b:
			print(i + 1, ans + 1)
		for i in c:
			print(i + 1, 2)
	else:
		print(o)
		if y != 0:
			ans = c[0]
		else:
			ans = a[0]
		for i in d:
			print(i + 1, ans + 1)
		for i in a:
			print(i + 1, 1)


import math
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	e = []
	o = []
	cte = 0
	cto = 0
	for i in range(n):
		if i % 2 == 0:
			e.append(0)
			o.append(1)
		else:
			e.append(1)
			o.append(0)
	a = []
	for i in range(n):
		if arr[i] % 2 == 0:
			a.append(0)
			cte += 1
		else:
			a.append(1)
			cto += 1
	if cto == 0:
		print(-1)
		continue
	if cto == n:
		print(n // 2)
		for i in range(n):
			if i % 2 == 1:
				print(i + 1, 1, sep=' ')
		continue
	diffe = 0
	diffo = 0
	for i in range(n):
		if a[i] != e[i]:
			diffe += 1
		else:
			diffo += 1
	if diffe < diffo:
		sup = e
		need_ch = diffe
	else:
		sup = o
		need_ch = diffo
	for i in range(n):
		if a[i] == 1 and a[i] == sup[i]:
			seco = i
			break
	for i in range(n):
		if a[i] == 0 and a[i] == sup[i]:
			sece = i
			break
	print(need_ch)
	for i in range(n):
		if a[i] == 0 and a[i] != sup[i]:
			print(i + 1, seco + 1, sep=' ')
		elif a[i] == 1 and a[i] != sup[i]:
			print(i + 1, seco + 1, sep=' ')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mp = -1
	a = []
	for i in range(n):
		a.append(arr[i] & 1)
		if a[i] == 1:
			mp = i
	if mp == -1:
		print(-1)
		continue
	a1 = []
	for i in range(1, n, 2):
		if a[i] == 0:
			a1.append([i + 1, mp + 1])
	for i in range(0, n, 2):
		if a[i] == 1:
			a1.append([i + 1, 2])
	a2 = []
	for i in range(0, n, 2):
		if a[i] == 0:
			a2.append([i + 1, mp + 1])
	for i in range(1, n, 2):
		if a[i] == 1:
			a2.append([i + 1, 1])
	if len(a1) > len(a2):
		a1 = a2
	print(len(a1))
	for i in a1:
		print(*i)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odd_index_odd = []
	odd_index_even = []
	even_index_odd = []
	even_index_even = []
	count = 0
	for i in range(n):
		if i % 2 == 0:
			if arr[i] % 2 == 0:
				even_index_even.append(i)
				count += 1
			else:
				even_index_odd.append(i)
		elif arr[i] % 2 == 0:
			odd_index_even.append(i)
			count += 1
		else:
			odd_index_odd.append(i)
	if count == n:
		print(-1)
		continue
	no_of_even_at_odd = len(odd_index_even)
	no_of_odd_at_even = len(even_index_odd)
	tot1 = no_of_even_at_odd + no_of_odd_at_even
	no_of_odd_at_odd = len(odd_index_odd)
	no_of_even_at_even = len(even_index_even)
	tot2 = no_of_odd_at_odd + no_of_even_at_even
	if tot1 < tot2:
		print(tot1)
		if no_of_odd_at_odd != 0:
			ind = odd_index_odd[0]
		else:
			ind = even_index_odd[0]
		for i in odd_index_even:
			print(i + 1, ind + 1)
		for i in even_index_odd:
			print(i + 1, 2)
	else:
		print(tot2)
		if no_of_odd_at_even != 0:
			ind = even_index_odd[0]
		else:
			ind = odd_index_odd[0]
		for i in even_index_even:
			print(i + 1, ind + 1)
		for i in odd_index_odd:
			print(i + 1, 1)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	a = []
	ce = 0
	co = 0
	pe = 0
	po = 0
	for i in range(n):
		if lst[i] % 2 == 0:
			a.append(0)
			ce = ce + 1
		else:
			a.append(1)
			co = co + 1
	if co == 0:
		print(-1)
	elif co == n:
		print(n // 2)
		j = 1
		while j < n:
			print(j + 1, 1)
			j = j + 2
	else:
		ans = []
		ans1 = []
		po1 = 0
		po2 = 0
		pe1 = 0
		pe2 = 0
		i = 0
		flag = 1
		while flag == 1 and i < n:
			if i % 2 == 0 and a[i] == 1:
				po1 = i
				flag = 0
			i = i + 1
		i = 0
		flag = 1
		while flag == 1 and i < n:
			if i % 2 == 1 and a[i] == 0:
				pe1 = i
				flag = 0
			i = i + 1
		i = 0
		flag = 1
		while flag == 1 and i < n:
			if i % 2 == 0 and a[i] == 0:
				pe2 = i
				flag = 0
			i = i + 1
		i = 0
		flag = 1
		while flag == 1 and i < n:
			if i % 2 == 1 and a[i] == 1:
				po2 = i
				flag = 0
			i = i + 1
		for i in range(len(lst)):
			if i % 2 == 0 and a[i] == 0:
				ans.append(i + 1)
				ans.append(po1 + 1)
			if i % 2 != 0 and a[i] == 1:
				ans.append(i + 1)
				ans.append(po1 + 1)
		for i in range(len(lst)):
			if i % 2 == 0 and a[i] == 1:
				ans1.append(i + 1)
				ans1.append(po2 + 1)
			if i % 2 != 0 and a[i] == 0:
				ans1.append(i + 1)
				ans1.append(po2 + 1)
		if min(len(ans1), len(ans)) == len(ans):
			print(len(ans) // 2)
			j = 0
			while j < len(ans):
				print(ans[j], ans[j + 1])
				j = j + 2
		else:
			print(len(ans1) // 2)
			j = 0
			while j < len(ans1):
				print(ans1[j], ans1[j + 1])
				j = j + 2


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	o = 0
	e = 0
	for i in range(n):
		if a[i] & 1:
			c += 1
			if i & 1:
				o += 1
			else:
				e += 1
	if c == 0:
		print(-1)
	elif o >= e:
		ans = []
		x = -1
		for i in range(n):
			if a[i] & 1 and i & 1:
				x = i
				break
		for i in range(n):
			if i & 1 and a[i] % 2 == 0 or (i % 2 == 0 and a[i] & 1):
				ans.append((i + 1, x + 1))
		print(len(ans))
		for i in ans:
			print(*i)
	else:
		ans = []
		x = -1
		for i in range(n):
			if a[i] & 1 and i % 2 == 0:
				x = i
				break
		for i in range(n):
			if i & 1 and a[i] & 1 or (i % 2 == 0 and a[i] % 2 == 0):
				ans.append((i + 1, x + 1))
		print(len(ans))
		for i in ans:
			print(*i)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	g = -1
	for x in range(len(l)):
		if x % 2 == 0 and l[x] % 2 == 0:
			cnt = cnt + 1
		elif x % 2 == 1 and l[x] % 2 == 1:
			cnt = cnt + 1
		if l[x] % 2 == 1:
			g = x
	if g == -1:
		print('-1')
	elif cnt <= int(len(l) / 2):
		print(cnt)
		if l[0] % 2 == 0:
			l[0] = l[0] ^ l[g]
			print('1', g + 1)
			g = 0
		else:
			g = 0
		for x in range(len(l)):
			if x % 2 == 0 and l[x] % 2 == 0:
				print(x + 1, g + 1)
			elif x % 2 == 1 and l[x] % 2 == 1:
				print(x + 1, g + 1)
	else:
		print(len(l) - cnt)
		if l[1] % 2 == 0:
			l[1] = l[1] ^ l[g]
			print('2', g + 1)
			g = 1
		else:
			g = 1
		for x in range(len(l)):
			if x % 2 == 1 and l[x] % 2 == 0:
				print(x + 1, g + 1)
			elif x % 2 == 0 and l[x] % 2 == 1:
				print(x + 1, g + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a = a[:n]
	even_a = 0
	even_b = 0
	indices = []
	op = 0
	for i in range(n):
		if a[i] % 2 == 0:
			if i % 2 == 0:
				even_a += 1
			else:
				even_b += 1
	if even_a > even_b:
		for i in range(n):
			if i % 2 == 0:
				if a[i] % 2 != 0:
					poss = False
					for j in range(n):
						if a[j] % 2 != 0 and i != j:
							a[i] = a[i] ^ a[j]
							indices.append([i + 1, j + 1])
							poss = True
							op += 1
							break
					if not poss:
						op = -1
						break
			elif a[i] % 2 == 0:
				poss = False
				for j in range(n):
					if a[j] % 2 != 0 and i != j:
						a[i] = a[i] ^ a[j]
						indices.append([i + 1, j + 1])
						poss = True
						op += 1
						break
				if not poss:
					op = -1
					break
	else:
		for i in range(n):
			if i % 2 != 0:
				if a[i] % 2 != 0:
					poss = False
					for j in range(n):
						if a[j] % 2 != 0 and i != j:
							a[i] = a[i] ^ a[j]
							indices.append([i + 1, j + 1])
							poss = True
							op += 1
							break
					if not poss:
						op = -1
						break
			elif a[i] % 2 == 0:
				poss = False
				for j in range(n):
					if a[j] % 2 != 0 and i != j:
						a[i] = a[i] ^ a[j]
						indices.append([i + 1, j + 1])
						poss = True
						op += 1
						break
				if not poss:
					op = -1
					break
	print(op)
	for i in indices:
		print(i[0], i[1])


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [x % 2 for x in arr]
	if len(set(arr)) == 1 and arr[0] == 0:
		print(-1)
		continue
	ans = []
	s1 = [0 for i in range(n)]
	s2 = [1 for i in range(n)]
	(cnt1, cnt2) = (0, 0)
	for i in range(n):
		if i & 1:
			s1[i] = 1
			s2[i] = 0
		if s1[i] != arr[i]:
			cnt1 += 1
		if s2[i] != arr[i]:
			cnt2 += 1
	mask = []
	if cnt1 <= cnt2:
		mask = s1[:]
	else:
		mask = s2[:]
	ind = arr.index(1)
	ind2 = mask.index(1)
	for i in range(n):
		if arr[i] == 0 and mask[i] == 1:
			ans.append((i + 1, ind + 1))
	for i in range(n):
		if arr[i] == 1 and mask[i] == 0:
			ans.append((i + 1, ind2 + 1))
	print(min(cnt1, cnt2))
	for i in range(len(ans)):
		print(*ans[i])


import copy

def findEven(arr):
	for i in arr:
		if i % 2 == 1:
			return False
	return True

def findOdd(arr, start):
	for j in range(start, len(arr), 2):
		if arr[j] % 2 == 1:
			return j

def change(arr, startodd, startEven, odd):
	for i in range(startodd, len(arr), 2):
		if arr[i] % 2 == 1:
			print(i + 1, odd)
	for i in range(startEven, len(arr), 2):
		if arr[i] % 2 == 0:
			print(i + 1, odd)
t = int(input())
test = []
for i in range(t):
	n = int(input())
	v = [int(j) for j in input().split()]
	test.append([n, v])
for i in test:
	if findEven(i[1]):
		print(-1)
		continue
	feven = 0
	fodd = 0
	seven = 0
	sodd = 0
	for j in range(0, i[0], 2):
		if i[1][j] % 2 == 1:
			fodd += 1
		else:
			feven += 1
	for j in range(1, i[0], 2):
		if i[1][j] % 2 == 1:
			sodd += 1
		else:
			seven += 1
	if feven + sodd > fodd + seven:
		ind = findOdd(i[1], 1)
		print(fodd + seven)
		change(i[1], 0, 1, ind + 1)
	else:
		ind = findOdd(i[1], 0)
		print(feven + sodd)
		change(i[1], 1, 0, ind + 1)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	flag = False
	for i in range(n):
		if A[i] % 2 == 1:
			A[i] = 1
		else:
			A[i] = 0
	first = []
	second = []
	no_alt_id1 = []
	no_alt_id2 = []
	for i in range(n):
		if i % 2 == 0 and A[i] == 0:
			pass
		elif i % 2 == 1 and A[i] == 1:
			no_alt_id1.append(i)
		else:
			first.append(i)
	for i in range(n):
		if i % 2 == 1 and A[i] == 0:
			pass
		elif i % 2 == 0 and A[i] == 1:
			no_alt_id2.append(i)
		else:
			second.append(i)
	ans = []
	if len(first) < len(second):
		for i in range(len(first)):
			if len(no_alt_id1) == 0:
				flag = True
				print(-1)
				break
			else:
				ans.append(first[i] + 1)
				ans.append(no_alt_id1[0] + 1)
	else:
		for i in range(len(second)):
			if len(no_alt_id2) == 0:
				flag = True
				print(-1)
				break
			else:
				ans.append(second[i] + 1)
				ans.append(no_alt_id2[0] + 1)
	if flag != True:
		print(len(ans) // 2)
		for i in range(0, len(ans), 2):
			print(ans[i], end=' ')
			print(ans[i + 1])