Mikhail walks on a Cartesian plane. He starts at the point $(0, 0)$, and in one move he can go to any of eight adjacent points. For example, if Mikhail is currently at the point $(0, 0)$, he can go to any of the following points in one move:   $(1, 0)$;  $(1, 1)$;  $(0, 1)$;  $(-1, 1)$;  $(-1, 0)$;  $(-1, -1)$;  $(0, -1)$;  $(1, -1)$. 

If Mikhail goes from the point $(x1, y1)$ to the point $(x2, y2)$ in one move, and $x1 \ne x2$ and $y1 \ne y2$, then such a move is called a diagonal move.

Mikhail has $q$ queries. For the $i$-th query Mikhail's target is to go to the point $(n_i, m_i)$ from the point $(0, 0)$ in exactly $k_i$ moves. Among all possible movements he want to choose one with the maximum number of diagonal moves. Your task is to find the maximum number of diagonal moves or find that it is impossible to go from the point $(0, 0)$ to the point $(n_i, m_i)$ in $k_i$ moves.

Note that Mikhail can visit any point any number of times (even the destination point!).


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of queries.

Then $q$ lines follow. The $i$-th of these $q$ lines contains three integers $n_i$, $m_i$ and $k_i$ ($1 \le n_i, m_i, k_i \le 10^{18}$) — $x$-coordinate of the destination point of the query, $y$-coordinate of the destination point of the query and the number of moves in the query, correspondingly.


-----Output-----

Print $q$ integers. The $i$-th integer should be equal to -1 if Mikhail cannot go from the point $(0, 0)$ to the point $(n_i, m_i)$ in exactly $k_i$ moves described above. Otherwise the $i$-th integer should be equal to the the maximum number of diagonal moves among all possible movements.


-----Example-----
Input
3
2 2 3
4 3 7
10 1 9

Output
1
6
-1



-----Note-----

One of the possible answers to the first test case: $(0, 0) \to (1, 0) \to (1, 1) \to (2, 2)$.

One of the possible answers to the second test case: $(0, 0) \to (0, 1) \to (1, 2) \to (0, 3) \to (1, 4) \to (2, 3) \to (3, 2) \to (4, 3)$.

In the third test case Mikhail cannot reach the point $(10, 1)$ in 9 moves.

Difficulty: interview

Starter code:

Solutions:
q=int(input())

for e in range(q):
    x,y,k=list(map(int,input().split()))
    x,y=abs(x),abs(y)
    x,y=max(x,y),min(x,y)
    
    if(x%2!=k%2):
        k-=1
        y-=1
    
    
    if(x>k):
        print(-1)
        continue
    if((x-y)%2):
        k-=1
        x-=1
    print(k)
    
    
    


#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except ModuleNotFoundError:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
Q, = getIntList()
for _ in range(Q):
    N, M, K  = getIntList()
    if max(N,M) >K:
        print(-1)
        continue
    r = K
    if N%2!= K%2:
        r-=1
    if M%2!= K%2:
        r-=1
    print(r)








q = int(input())
for i in range(q):
    x, y, k = list(map(int, input().split()))
    if x > y: x, y = y, x
    m = y
    d = y
    if (y - x) % 2 == 1:
        d -= 1
    if k < m:
        print(-1)
        continue
    r = k - m
    if r % 2 != 0:
        r -= 1
        if d != m:
            d += 1
        else:
            d -= 1
    d += r
    print(d)


q = int(input())
otvet = []
for i in range(q):
    g = input().split()
    n = int(g[0])
    m = int(g[1])
    k = int(g[2])
    if n < 0:
        n = -n
    if m < 0:
        m = -m
    if m > k or n > k:
        otvet.append(-1)
    elif m % 2 == k % 2 and n % 2 == k % 2:
        otvet.append(k)
    elif m % 2 == k % 2 or n % 2 == k % 2:
        otvet.append(k - 1)
    else:
        otvet.append(k - 2)
for i in otvet:
    print(i)


q = int(input())
for i in range(q):
    a, b, k = list(map(int, input().split()))
    if a < b:
        a, b, = b, a
    if a > k:
        print(-1)
    elif a % 2 == b % 2 != k % 2:
        print(k - 2)
    elif (a + b) % 2 != 0:
        print(k - 1)
    else:
        print(k)


q = int(input())
for i in range(q):
    n, m, k = list(map(int, input().split()))
    m, n = abs(m), abs(n)
    mx = max(m, n)
    remaining = k - mx
    if remaining < 0:
        print(-1)
    elif m == n == 0:
        if k == 1:
            print(-1)
        elif k % 2:
            print(k - 1)
        else:
            print(k)
    elif abs(m - n) % 2 == 0:
        if remaining % 2 == 0:
            print(k)
        else:
            print(k - 2)
    else:
        if not remaining:
            print(k - 1)
        elif remaining % 2 == 0:
            print(k - 1)
        else:
            print(k - 1)


from collections import deque
from sys import stdin
lines = deque(line.strip() for line in stdin.readlines())

def nextline():
    return lines.popleft()

def types(cast, sep=None):
    return tuple(cast(x) for x in strs(sep=sep))

def ints(sep=None):
    return types(int, sep=sep)

def strs(sep=None):
    return tuple(nextline()) if sep == '' else tuple(nextline().split(sep=sep))

def main():
    # lines will now contain all of the input's lines in a list
    T = int(nextline())
    for testCase in range(1, T + 1):
        n, m, k = ints()
        min_k = max(n, m)
        if min_k > k:
            print(-1)
            continue
        if (n - m) % 2 == 0:
            if k % 2 == n % 2:
                print(k)
                continue
            print(k - 2)
            continue
        print(k - 1)

def __starting_point():
    main()

__starting_point()



q = int(input())

for _ in range(q):
    n, m, k = list(map(int, input().split()))
    if max([n, m]) > k:
        print(-1)
    else:
        if (n + m) % 2 == 0:
            if max([n, m]) % 2 != k % 2:
                print(k - 2)
            else:
                print(k)
        else:
            print((k - 1));


import math

q = int(input())

for i in range(q):
    x, y, k = map(int, input().split())
    if x > k or y > k:
        print(-1)
    else:
        if (x+y)%2 == 0:
            if (k-max(x,y)) % 2 == 0:
                print(k)
            else:
                print(k - 2)
        else:
            if (k-max(x,y)) % 2 == 0:
                print(k-1)
            else:
                print(k-1)

q = int(input())

for _ in range(q):
    n, m, k = list(map(int, input().split()))
    if k == 0:
        if n == 0 and m == 0:
            print(0)
        else:
            print(-1)
    elif k == 1:
        if max(abs(n), abs(m)) != 1:
            print(-1)
        elif abs(n) == abs(m) == 1:
            print(1)
        else:
            print(0)
    else:
        if max(abs(n), abs(m)) > k:
            print(-1)
        elif abs(n) == abs(m):
            if (k - abs(n)) % 2 == 0:
                print(k)
            else:
                print(k - 2)
        elif (max(abs(n), abs(m)) - min(abs(n), abs(m))) % 2 == 0:
            if (k - max(abs(n), abs(m))) % 2 == 0:
                print(k)
            else:
                print(k - 2)
        else:
            print(k - 1)






import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

for _ in range(int(input())):
    n,m,k=list(map(int,input().split()))
    n=abs(n)
    m=abs(m)
    if max(n,m)>k:
        print("-1")
    else:
        # you can't 0 0 1 me :D
        bad1=((n+k)%2==1)
        bad2=((m+k)%2==1)
        print(k-bad1-bad2)


USE_STDIO = False

if not USE_STDIO:
    try: import mypc
    except: pass

def main():
    q,  = list(map(int, input().split(' ')))
    for _ in range(q):
        n, m, k = list(map(int, input().split(' ')))
        if n > k or m > k:
            print(-1)
        elif (n - m) % 2:
            print(k - 1)
        elif (n - k) % 2:
            print(k - 2)
        else:
            print(k)

def __starting_point():
    main()




__starting_point()

q=int(input())

Q=[list(map(int,input().split())) for i in range(q)]

for n,m,k in Q:
    if n>k or m>k:
        print(-1)
        continue

    x=max(n,m)-min(n,m)
    y=k-max(n,m)

    if x%2==0 and y%2==0:
        print(k)
    elif x%2==0 and y%2==1:
        print(k-2)
    elif x%2==1 and y%2==0:
        print(k-1)
    elif x%2==1 and y%2==1:
        print(k-1)


n = int(input())
for i in range(n):
    a, b, c = [int(el) for el in input().split()]
    if ( a > c or b > c):
        print(-1)
    else:
        if (a% 2 + b % 2 == 1):
            print(c - 1)
        elif (a%2 == b%2 == c%2):
            print(c)
        else:
            print(c - 2)


Q = int(input())
src = [tuple(map(int,input().split())) for i in range(Q)]
ans = []
for x,y,k in src:
    d = max(x,y)
    if (x+y)%2:
        ans.append(-1 if d > k else k-1)
    else:
        if d > k:
            ans.append(-1)
        else:
            ans.append(k-2 if (d+k)%2 else k)

print(*ans,sep='\n')


def m():
	[x, y, k] = [int(i) for i in input().split()]
	d=min(x, y)
	x-=d
	y-=d
	k-=d
	
	if k-x-y<0:
		print(-1)
	else:
		x+=y
		if x%2 > 0 and k%2>0:
			print(d+k-1)
		elif x%2 >0:
			print(d+k-1)
		elif k%2>0:
			print(d+k-2)
		else:
			print(d+k)
			
		
			
	
n=int(input())
for i in range(n):
	m()

q = int(input())

for i in range(q):
    (x, y, k) = list(map(int, input().split()))

    if max(x, y) > k:
        print(-1)
    elif x == y and k == x + 1:
        print(k - 2)
        continue
    elif x % 2 == 1 and y % 2 == 1 and k % 2 == 0:
        print(k - 2)
        continue
    elif x % 2 == 0 and y % 2 == 0 and k % 2 == 1:
        print(k - 2)
        continue
    elif (x + y) % 2 == 0:
        print(k)
    else:
        print(k - 1)


n = int(input())
for q in range(n):
    x, y, k = list(map(int, input().split()))
    if max(x, y) > k:
        print(-1)
    else:
        if 0 == (x + y) % 2:
            if k % 2 == max(x, y) % 2:
                print(k)
            else:
                print(k - 2)
        else:
            print(k - 1)


def go():
    n = int(input())
    for i in range(n):
        a, b, d = [int(i) for i in input().split(' ')]
        if a > d or b > d:
            print(-1)
        elif a % 2 == b % 2:
            if a % 2 == d % 2:
                print(d)
            else:
                print(d - 2)
        else:
            if a % 2 == b % 2:
                if d % 2 == a % 2:
                    print(d)
                else:
                    print(d - 2)
            else:
                print(d - 1)
go()


q = int(input())

for i in range(q):
    n, m, k = map(int, input().split())
    p = min(m, n)
    r = max(n, m) - p
    if (p+r) > k:
        print(-1)
    elif r % 2 == 1:
        print(k - 1)
    elif (k - p) % 2 == 0:
        print(k)
    else:
        print(k - 2)

q = int(input())
for i in range(q):
	n, m, k = map(int, input().split())
	ost = max(n, m) - min(n, m)
	plus = 0
	if ost % 2 != 0:
		plus = 1
		ost -= 1
	mini = min(n, m) + ost + plus
	#print('mini: ' + str(mini))
	if k < mini:
		print(-1)
	elif (k - mini) % 2 == 0 or plus == 1:
		print(k - plus)
	else:
		print(k - plus - 2)	

q=int(input())

for i in range(q):
	n,m,k=list(map(int,input().split()))

	if n>k or m>k:
		print(-1)

	else:
		if n%2==0 and m%2==0:
			if k%2==0:
				print(k)
			else:
				print(k-2)

		elif (n%2==0 and m%2==1) or (n%2==1 and m%2==0):
			print(k-1)

		elif n%2==1 and m%2==1:
			if k%2==0:
				print(k-2)
			else:
				print(k)


q=int(input())
for i in range(q):
    n, m, k = map(int, input().split())
    ans=max(n,m)
    diff=k-ans
    if diff<0:
        print(-1)
    else:
        if (n%2==0 and m%2==0) or (n%2!=0 and m%2!=0):
            if diff%2==0:
                ans+=diff
            else:
                ans+=diff-2
        else:
            ans+=diff-1
        print(ans)

"""
KA      YM        KA        AS      KA  ASKA      YASK        KA         SKAYMA   
KA    KA         SKAY        SK    SK   AS AY    AY SK       SKAY       AS    AS  
KA  AS          AS  YM        KA  AS    AS  YM  KA  SK      AS  YM      AS        
KAYM           MA    MA        AYMA     AS   MASK   SK     MA    MA      SKAYMA   
KA  AS        YMASKAYMAS        YM      AS    AS    SK    YMASKAYMAS          AS  
KA    KA     AY        SK       YM      AS          SK   AY        SK   AS    AS  
KA      YM  KA          KA      YM      AS          SK  KA          KA   SKAYMA   
"""
n=int(input())
for i in range(n):
	x,y,k=map(int,input().split())
	x,y=abs(x),abs(y)
	min_moves=max(x,y)
	if min_moves>k:
		print(-1)
	else:
		ans=min(x,y)
		x-=ans
		y-=ans
		p=max(x,y)
		k-=ans
		if k==p and p%2==0:
			print(ans+k)
		elif k==p and p%2==1:
			print(ans+k-1)
		elif p%2==0 and k%2==0:
			print(ans+k)
		elif p%2==0 and k%2==1:
			print(ans+k-2)
		elif p%2==1:
			print(ans+k-1)