Given a triangle of numbers where each number is equal to the sum of the three numbers on top of it, find the first even number in a row.  

Explanatory Note:
The vertex of the triangle (at the top) is 1.
The structure of the triangle is shown below.
Each number is equal to the sum of the numbers at the following positions:
Position X: immediately above it.
Position Y: to the immediate left of X.
Position Z: to the immediate right of X.
If there are no numbers at positions X, Y, or Z, then assume those positions are occupied by a zero (0). This can occur for positions at the edge.

Here are four rows of the triangle:

         1
      1  1  1
   1  2  3  2  1
1  3  6  7  6  3  1

Input Format and Constraints 

First line contains a number T (number of test cases).

Each of the next T lines contain a number N (the row number, assuming that the top vertex of the triangle is Row 1).

Output Format 

For each test case, display an integer that denotes the position of the first even number. 

Note: Assume that the left most number in a row is Position 1.

If there is no even number in a row, print -1.

Constraints 

1<=T<=100 

3<=N<=1000000000  

Sample Input  

2
3
4

Sample Output  

2
3

Difficulty: MEDIUM
Tags: Matrices

Starter code:

Solutions:
def number(n):
	if n == 1 or n == 2:
		return -1
	elif n % 2 == 1:
		return 2
	elif n % 4 == 0:
		return 3
	else:
		return 4
n = int(input())
row_num = []
for i in range(n):
	row_num.append(int(input()))
for j in range(n):
	print(number(row_num[j]))


[print('3242'[int(input()) & 3]) for cas in range(int(input()))]


import sys
t = int(sys.stdin.readline())
for i in range(0, t):
	x = int(sys.stdin.readline())
	if x % 2 == 1:
		print(2)
	elif x % 4 == 0:
		print(3)
	else:
		print(4)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


T = int(input())
for i in range(T):
	n = int(input())
	if n <= 2:
		print(-1)
	elif n % 2 != 0:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


t = int(input())
for m in range(t):
	n = int(input()) - 3
	if n < 0:
		print(-1)
	else:
		n = n % 4
		if n % 2 == 0:
			print(2)
		elif n == 1:
			print(3)
		else:
			print(4)


def function(pos):
	poses = [2, 3, 2, 4]
	if pos < 3:
		print(-1)
	else:
		pos -= 3
		pos %= 4
		print(poses[pos])
T = int(input())
for i in range(T):
	a = int(input())
	function(a)


mods = {0: 3, 1: 2, 2: 4, 3: 2}
for i in range(int(input())):
	n = int(input())
	if n < 3:
		print('-1')
	else:
		print(mods[n % 4])


T = int(input())
for t in range(0, T):
	n = int(input())
	if n < 3:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


numtests = int(input())
tests = []
for i in range(numtests):
	tests.append(int(input()))
for test in tests:
	if test == 1 or test == 2:
		print(-1)
	elif test % 2 != 0:
		print(2)
	elif test % 4 == 0:
		print(3)
	else:
		print(4)


T = int(input())
for i in range(0, T):
	N = int(input())
	if N % 2 != 0:
		print('2')
	elif N % 4 == 0:
		print('3')
	else:
		print('4')


numCases = int(input())
for _ in range(numCases):
	row = int(input())
	if row % 2 == 1:
		print(2)
	elif row % 4 == 0:
		print(3)
	else:
		print(4)


import sys
T = int(sys.stdin.readline())
for case in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 1:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


t = int(input())
for _ in range(t):
	n = int(input())
	ans = -1
	if n % 2 == 1:
		ans = 2
	elif n * (n - 1) // 2 % 2 == 0:
		ans = 3
	else:
		ans = 4
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


import sys
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	elif (n - 6) % 4 == 0:
		print(4)


T = int(input())
for t in range(T):
	row_num = int(input())
	if row_num < 3:
		print(-1)
		continue
	else:
		row_num -= 3
		if row_num % 2 == 0:
			print(2)
		elif row_num % 4 == 1:
			print(3)
		elif row_num % 4 == 3:
			print(4)


t = int(input())
for each_case in range(0, t):
	row_no = int(input())
	if row_no % 2 == 1:
		print(2)
	elif row_no % 4 == 0:
		print(3)
	else:
		print(4)


def f(N):
	if N == 1:
		return -1
	if N == 2:
		return -1
	if N % 2 != 0:
		return 2
	if N % 4 == 0:
		return 3
	else:
		return 4
t = int(input())
l = []
for i in range(t):
	s = int(input())
	l.append(f(s))
for i in l:
	print(i)


import sys
data = [int(x) for x in sys.stdin.read().strip().split()]
for x in data[1:]:
	if x == 1 or x == 2:
		print('-1')
	elif (x - 2) % 4 == 1:
		print('2')
	elif (x - 2) % 4 == 2:
		print('3')
	elif (x - 2) % 4 == 3:
		print('2')
	elif (x - 2) % 4 == 0:
		print('4')


for ans in range(int(input())):
	a = int(input())
	if a % 4 == 0:
		print(3)
	elif a % 4 == 1 or a % 4 == 3:
		print(2)
	else:
		print(4)


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


n = int(input())
for _ in range(int(n)):
	x = int(input())
	if x % 2 == 1:
		print(2)
	elif x / 2 % 2 == 1:
		print(4)
	else:
		print(3)


n = int(input())
s = 0
for i in range(n):
	inp = int(input())
	if inp == 1 or inp == 2:
		s = 0
	elif inp % 2 == 1:
		s = 2
	elif inp % 4 == 0:
		s = 3
	else:
		s = 4
	print(s)


cases = int(input())
for case in range(cases):
	n = int(input())
	ans = [3, 2, 4, 2]
	if n < 3:
		print(-1)
	else:
		print(ans[n & 3])


for i in range(int(input())):
	print((2, 3, 2, 4)[(int(input()) - 3) % 4])


def solve(N):
	if N < 3:
		return -1
	return {0: 2, 1: 3, 2: 2, 3: 4}[(N - 3) % 4]
t = int(input())
for i in range(t):
	print(solve(int(input())))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


t = int(input())
while t != 0:
	t = t - 1
	num = int(input())
	if num % 2 == 1:
		print(2)
	elif num % 4 == 0:
		print(3)
	else:
		print(4)


T = input()
for i in range(int(T)):
	N = input()
	if (int(N) / 2).is_integer() == False:
		print(2)
	elif int(N) % 4 == 0:
		print(3)
	else:
		print(4)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


def firsteven(n):
	if n % 2 == 1:
		return 2
	elif n % 4 == 0:
		return 3
	else:
		return 4

def run():
	t = int(input())
	while t > 0:
		t -= 1
		n = int(input())
		print(firsteven(n) if n > 1 else -1)
run()


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


T = int(input())
for _ in range(T):
	N = int(input())
	if N % 2 == 1:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


def main():
	for case in range(int(input())):
		n = int(input())
		print(check(n))

def check(n):
	if n == 1 or n == 2:
		return -1
	if n % 2 == 1:
		return 2
	if n % 2 == 0:
		if n / 2 % 2 == 0:
			return 3
		if n / 2 % 2 == 1:
			return 4
	return -1
main()


test = int(input())
for t in range(test):
	n = int(input())
	p = n % 4
	if p == 0:
		print(3)
	elif p == 1 or p == 3:
		print(2)
	else:
		print(4)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


Input_Data = int(input())
for i in range(Input_Data):
	a = int(input())
	if a == 1 or a == 2:
		print('-1')
	elif a % 2 == 1:
		print('2')
	elif a % 4 == 0:
		print('3')
	else:
		print('4')


t = int(input())
r = [None for i in range(t)]
for i in range(t):
	n = int(input()) - 1
	if n % 2 == 0:
		r[i] = 2
	elif (n + 1) % 4 == 0:
		r[i] = 3
	else:
		r[i] = 4
for i in range(t):
	print(r[i])


for i in range(int(input())):
	n = (int(input()) - 2) % 4
	if n % 2 == 1:
		print(2)
	elif n == 2:
		print(3)
	else:
		print(4)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	if n <= 2:
		print('-1')
	elif n % 2 == 1:
		print('2')
	elif n % 4 == 0:
		print('3')
	else:
		print('4')


x = int(input())
l = []
while x != 0:
	l.append(input())
	x = x - 1
for i in l:
	c = int(i)
	y = 2 * c - 1
	if c % 2 == 0:
		j = c / 2
		if j % 2 != 0:
			print('4')
		else:
			print('3')
	elif c % 2 != 0:
		print('2')


t = int(input())
for _ in range(t):
	n = int(input())
	if n < 3:
		print(-1)
	elif n % 4 == 0:
		print(3)
	elif n % 2 == 0:
		print(4)
	else:
		print(2)


from collections import deque

def next_level(a):
	middle = [None] * (len(a) - 2)
	l_end = a[0] + a[1]
	r_end = a[-1] + a[-2]
	temp = deque(a[0:3], maxlen=3)
	for i in range(len(middle)):
		middle[i] = sum(temp)
		try:
			temp.append(a[i + 3])
		except:
			pass
	return [1] + [l_end] + middle + [r_end] + [1]

def produce_level(x):
	level = 2
	current_level = [1, 1, 1]
	while level < x:
		current_level = next_level(current_level)
		level += 1
	return current_level

def find_starting_even(x):
	if x % 2:
		return 2

	def even_check(n):
		return n % 2
	current_level = produce_level(x)
	modulos = list(map(even_check, current_level))
	for (index, element) in enumerate(modulos):
		if element == 0:
			return index + 1
		else:
			pass
num_of_cases = int(input())
for i in range(num_of_cases):
	x = int(input())
	if x % 2:
		print(2)
	elif x % 4:
		print(4)
	else:
		print(3)


T = int(input())
dic = {0: 2, 1: 3, 2: 2, 3: 4}
for _ in range(T):
	N = int(input())
	print(dic[(N - 3) % 4])


def calc(row):
	if row % 2 > 0:
		return 2
	elif row % 4 == 0:
		return 3
	else:
		return 4
t = int(input())
for i in range(t):
	row = int(input())
	print(calc(row))


t = int(input())
for i in range(0, t):
	f = int(input())
	if f == 1 or f == 2:
		print(-1)
	else:
		if f & 1 == 1:
			print('2')
		if f & 1 == 0 and f & 3 != 0:
			print('4')
		if f & 3 == 0:
			print('3')


T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1 or N == 2:
		print('-1')
	elif N % 2 != 0:
		print('2')
	elif (N - 2) % 4 == 0:
		print('4')
	elif N % 2 == 0:
		print('3')


T = int(input())
for _ in range(T):
	N = int(input()) - 1
	if not N % 2:
		print(2)
	elif not (N - 1) % 4:
		print(4)
	else:
		print(3)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


T = int(input())
for _ in range(T):
	t = int(input())
	if t % 2 == 1:
		print(2)
	elif t % 4 == 0:
		print(3)
	else:
		print(4)


cnt = int(input())

def create_triangle_row(row_num):
	current_row = 1
	current_line = []
	prev_line = []
	while current_row <= row_num:
		current_line = []
		if current_row == 1:
			current_line = [1]
		elif current_row == 2:
			current_line = [1, 1, 1]
		else:
			count_items = len(prev_line) + 2
			if count_items > 6:
				count_items = 6
			for idx in range(count_items):
				value = 0
				if idx == 0:
					value = prev_line[0]
				elif idx == 1:
					value = prev_line[0] + prev_line[1]
				elif idx == count_items - 1:
					value = prev_line[len(prev_line) - 1]
				elif idx == count_items - 2:
					value = prev_line[len(prev_line) - 1] + prev_line[len(prev_line) - 2]
				else:
					value = prev_line[idx - 2] + prev_line[idx - 1] + prev_line[idx]
				current_line.append(value)
		prev_line = current_line
		current_row += 1
	return current_line

def found_even(lst):
	idx = 1
	for ind in lst:
		if ind % 2 == 0:
			return idx
		idx += 1
	return -1
for idx in range(cnt):
	row_num = int(input())
	if row_num % 4 == 0:
		print(3)
	elif row_num % 2 == 1:
		print(2)
	else:
		print(4)


for _ in range(int(input())):
	N = int(input())
	if N % 2 != 0:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


n = int(input())
for i in range(n):
	k = int(input())
	if k % 2 != 0:
		print(2)
	elif k % 4 == 0:
		print(3)
	else:
		print(4)


t = int(input())
for x in range(t):
	n = int(input())
	if (n - 2) % 2 != 0:
		print(2)
	elif (n - 2) % 4 == 0:
		print(4)
	else:
		print(3)


key = [3, 2, 4, 2]
for _ in range(int(input())):
	print(key[int(input()) % 4])


T = int(input())
idx = [3, 2, 4, 2]
for _ in range(T):
	N = int(input())
	print(idx[N % 4])


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


for x in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print('2')
	elif n % 4 == 0:
		print('3')
	else:
		print('4')


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print('2')
	elif n % 4 == 0:
		print('3')
	else:
		print('4')


for _ in range(int(input().strip())):
	n = int(input().strip())
	if n <= 2:
		print(-1)
		continue
	print([3, 2, 4, 2][n % 4])


d = {}
d[1] = [1]
d[2] = [1, 1, 1]
for i in range(3, 30):
	for j in range(i):
		if j == 0:
			d[i] = [1]
		elif j == 1:
			d[i] += [d[i - 1][0] + d[i - 1][1]]
		else:
			d[i] += [d[i - 1][j - 2] + d[i - 1][j - 1] + d[i - 1][j]]
	d[i] += d[i][:-1][::-1]
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(-1)
	else:
		t = n - 3
		if t % 4 == 0 or t % 4 == 2:
			print(2)
		elif t % 4 == 1:
			print(3)
		elif t % 4 == 3:
			print(4)


N = int(input())
L = []
for i in range(N):
	L.append(int(input()) - 1)
for lin in L:
	if lin % 2 == 0:
		print(2)
	elif (lin - 1) % 4 == 0:
		print(4)
	else:
		print(3)


t = int(input())
for i in range(t):
	n = int(input())
	if n <= 2:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n * (n + 1) // 2 % 2 == 0:
		print(3)
	else:
		print(4)


for _ in range(int(input())):
	N = int(input())
	if N & 1:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	if n <= 2:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n % 2 == 0:
		if n // 2 % 2 == 0:
			print(3)
		else:
			print(4)


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


t = int(input())
tests = []
for i in range(t):
	tests.append(int(input()))
for t in tests:
	seq = [2, 3, 2, 4]
	pos = t % 4 - 3
	print(seq[pos])


for _ in range(int(input())):
	print([3, 2, 4, 2][int(input()) % 4])


T = int(input().strip())
for t in range(0, T):
	N = int(input().strip())
	if N % 2 == 1:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


print(*((lambda x: -1 if x < 3 else 2 if x % 2 else 4 if x % 4 else 3)(int(input())) for _ in range(int(input()))), sep='\n')


for _ in range(int(input())):
	N = int(input())
	if N <= 2:
		print(-1)
	else:
		print({0: 3, 1: 2, 2: 4, 3: 2}[N % 4])


def even_pos(n):
	temp = n % 4
	if temp == 0:
		return 3
	if temp == 2:
		return 4
	return 2
out = []
T = int(input())
for t in range(T):
	out.append(even_pos(int(input())))
for o in out:
	print(o)


T = int(input())
for _ in range(T):
	v = int(input())
	if v == 1 or v == 2:
		print(-1)
	elif v % 2 == 1:
		print(2)
	elif v % 4 == 0:
		print(3)
	elif (v + 2) % 4 == 0:
		print(4)


for i in range(int(input())):
	print([3, 2, 4, 2][int(input()) % 4])


T = int(input())
for t in range(T):
	N = int(input())
	if (N - 1) % 2 == 0:
		print(2)
	elif (N - 1) % 4 == 3:
		print(3)
	else:
		print(4)


ans = []
for i in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		c = 2
	elif n % 4 == 0:
		c = 3
	else:
		c = 4
	ans.append(c)
for i in ans:
	print(i)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		if n / 2 % 2 == 0:
			print(3)
		else:
			print(4)
	else:
		print(2)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	if N % 2 == 0:
		print(3 if N // 2 % 2 == 0 else 4)
	else:
		print(2)


import sys

def solve(n):
	if n == 1 or n == 2:
		return -1
	x = n % 4
	if x == 1 or x == 3:
		return 2
	if x == 0:
		return 3
	if x == 2:
		return 4
tc_len = int(sys.stdin.readline())
for tc in range(tc_len):
	n = int(sys.stdin.readline())
	print(solve(n))


T = int(input())
for i in range(T):
	N = int(input())
	if N % 2 == 1:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


inf = float('inf')
read_ints = lambda : list(map(int, input().split()))

def solve(N):
	if N <= 2:
		return -1
	if N % 2 == 1:
		return 2
	if N % 4 == 0:
		return 3
	return 4
T = int(input())
for _ in range(T):
	N = int(input())
	print(solve(N))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if (n - 1) % 2 == 0:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


T = int(input().strip())
for _ in range(T):
	row = int(input().strip())
	if row % 2 != 0:
		position = 2
	elif row % 4 == 0:
		position = 3
	elif row % 2 == 0 and row % 4 != 0:
		position = 4
	else:
		position = -1
	print(position)


T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	if N % 2 != 0:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)


t = int(input())
while t:
	p = int(input())
	if p == 1 or p == 2:
		print(-1)
	elif p % 4 == 3:
		print(2)
	elif p % 4 == 0:
		print(3)
	elif p % 4 == 1:
		print(2)
	elif p % 4 == 2:
		print(4)
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	if n < 3:
		print(-1)
	elif n % 2 == 1:
		print(2)
	elif n % 4 == 0:
		print(3)
	else:
		print(4)


b = int(input())

def mathh(n):
	if n % 2 != 0:
		print(2)
	elif n % 4 == 0:
		print(3)
	elif n % 4 == 2:
		print(4)
for i in range(b):
	i = int(input())
	mathh(i)


for i in range(int(input())):
	a = int(input())
	if a <= 2:
		print(-1)
	elif a % 2 != 0:
		print(2)
	elif a % 4 == 0:
		print(3)
	else:
		print(4)


T = int(input())
for test in range(T):
	N = int(input())
	if N < 3:
		print('-1')
	elif N % 2 == 1:
		print('2')
	elif N % 4 == 0:
		print('3')
	else:
		print('4')


cycle = [2, 3, 2, 4]
for _ in range(int(input())):
	n = int(input())
	print(-1 if n <= 2 else cycle[(n - 3) % 4])


for i in range(int(input())):
	a = int(input())
	if a == 1 or a == 2:
		print(-1)
	elif a % 4 == 0:
		print(3)
	elif a % 2 != 0:
		print(2)
	else:
		print(4)


T = int(input())
for _ in range(T):
	N = int(input())
	if N % 2 == 1:
		print(2)
	elif N // 2 % 2 == 1:
		print(4)
	else:
		print(3)


for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(-1)
	elif n == 3:
		print(2)
	else:
		if n % 4 == 0:
			print(3)
		if n % 4 == 1:
			print(2)
		if n % 4 == 2:
			print(4)
		if n % 4 == 3:
			print(2)


T = int(input())
for t in range(T):
	N = int(input())
	if N % 2:
		print(2)
	elif N % 4 == 0:
		print(3)
	else:
		print(4)