Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

You have to answer $q$ independent queries.

Let's see the following example: $[1, 3, 4]$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $4$ candies, and Bob has $4$ candies.

Another example is $[1, 10, 100]$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $54$ candies, and Alice takes $46$ candies. Now Bob has $55$ candies, and Alice has $56$ candies, so she has to discard one candy — and after that, she has $55$ candies too.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 1000$) — the number of queries. Then $q$ queries follow.

The only line of the query contains three integers $a, b$ and $c$ ($1 \le a, b, c \le 10^{16}$) — the number of candies in the first, second and third piles correspondingly.


-----Output-----

Print $q$ lines. The $i$-th line should contain the answer for the $i$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).


-----Example-----
Input
4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45

Output
4
55
15000000000000000
51

Difficulty: introductory

Starter code:

Solutions:
from sys import stdin,stdout
import sys
import math

t=int(stdin.readline())
for i in range(t):
    a=list(map(int,stdin.readline().split()))
    print(sum(a)//2)



































for i in range(int(input())):
    a = list(map(int, input().split()))
    print((a[0] + a[1] + a[2]) // 2)


ll= lambda : list(map(int,input().split()))
testcases=1
testcases=int(input())
for testcase in range(testcases):
    [a,b,c]=ll()
    print((a+b+c)//2)


import sys
# sys.stdin.readline()
t=int(sys.stdin.readline())
for i in range(t):
    a=list(map(int,sys.stdin.readline().strip().split()))
    op=sum(a)
    print(op//2)


t=int(input())
for i in range(0,t):
	l=list(map(int,input().split()))
	s=sum(l)
	s=s//2
	print(s)

mod = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n=ii()
for i in range(n):
    a,b,c=f()
    print((a+b+c)//2)

for _ in range(int(input())):
    a,b,c=map(int,input().split())
    print((a+b+c)//2)

n = int(input())
for _ in range(n):
	l = list(map(int, input().split()))
	s = sum(l)
	print(s // 2)

n = int(input())
for i in range(n):
    a, b, c = map(int, input().split())
    print((a+b+c)//2)

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 14 12:40:58 2019

@author: Hamadeh
"""
class cinn:
    def __init__(self):
        self.x=[]
    def cin(self,t=int):
        if(len(self.x)==0):
            a=input()
            self.x=a.split()
            self.x.reverse()
        return self.get(t)
    def get(self,t):
        return t(self.x.pop())
    def clist(self,n,t=int): #n is number of inputs, t is type to be casted
        l=[0]*n
        for i in range(n):
            l[i]=self.cin(t)
        return l
    def clist2(self,n,t1=int,t2=int,t3=int,tn=2):
        l=[0]*n
        for i in range(n):
            if(tn==2):
                a1=self.cin(t1)
                a2=self.cin(t2)
                l[i]=(a1,a2)
            elif (tn==3):
                a1=self.cin(t1)
                a2=self.cin(t2)
                a3=self.cin(t3)
                l[i]=(a1,a2,a3)
        return l
    def clist3(self,n,t1=int,t2=int,t3=int):
        return self.clist2(self,n,t1,t2,t3,3)
    def cout(self,i,ans=''):   
        if(ans==''):
            print("Case #"+str(i+1)+":", end=' ')
        else:
            print("Case #"+str(i+1)+":",ans)
    def printf(self,thing):
        print(thing,end='')
    def countlist(self,l,s=0,e=None):
        if(e==None):
            e=len(l)
        dic={}
        for el in range(s,e):
            if l[el] not in dic:
                dic[l[el]]=1
            else:
                dic[l[el]]+=1
        return dic
    def talk (self,x):
        print(x,flush=True)
    def dp1(self,k):
        L=[-1]*(k)
        return L
    def dp2(self,k,kk):
        L=[-1]*(k)
        for i in range(k):
            L[i]=[-1]*kk
        return L
    def isprime(self,n):
        if(n==1 or n==0):
            return False
        for i in range(2,int(n**0.5+1)):
            if(n%i==0):
                return False
        return True
    def factors(self,n):    
        from functools import reduce
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    def nthprime(self,n):
        #usable up to 10 thousand
        i=0
        s=2
        L=[]
        while(i<n):
            while(not self.isprime(s)):
                s+=1
            L.append(s)
            s+=1
            i+=1
        return L
    def matrixin(self,m,n,t=int):
        L=[]
        for i in range(m):
            p=self.clist(n,t)
            L.append(p)
        return L
    def seive(self,k):
        #1000000 tops
        n=k+1
        L=[True]*n
        L[1]=False
        L[0]=False
        for i in range(2,n):
            if(L[i]==True):
                for j in range(2*i,n,i):
                    L[j]=False
        return L
    def seiven(self,n,L):
        i=0
        for j in range(len(L)):
            if(L[j]==True):
                i+=1
            if(i==n):
                return j
    def matrixin2(self,m,t=int):
        L=[]
        for i in range(m):
            iny=self.cin(str)
            lsmall=[]
            for el in iny:
                lsmall.append(t(el))
            L.append(lsmall)
        return L
c=cinn()
que=c.cin()
for i in range(que):
    q=c.cin()
    x=c.cin()
    z=c.cin()
    print((x+z+q)//2)

q=int(input())
for i in range(q):
	a,b,c=map(int,input().split())
	print ((a+b+c)//2)

for i in range(int(input())):
    a,b,c=map(int, input().split())
    print((a+b+c)//2)

q = int(input())
for Q in range(q):
    A = [int(i) for i in input().split()]
    A.sort()
    alice = A[0]
    bob = A[1]
    excess = A[2]

    total = sum(A)

    each = total//2

    print(each)


import sys
input = lambda: sys.stdin.readline().strip()

T = int(input())
for i in range(T):
    a, b, c = list(map(int, input().split()))
    print((a+b+c)//2)


Q = int(input())
for _ in range(Q):
    a, b, c = list(map(int, input().split()))
    print((a+b+c)//2)



from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b):
    return abs(a[0]-b[0])+abs(b[1]-a[1])

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def eld(x,y):
    a = y[0]-x[0]
    b = x[1]-y[1]
    return (a*a+b*b)**0.5

def lgcd(a):
    g = a[0]
    for i in range(1,len(a)):
        g = math.gcd(g,a[i])
    return g

def ms(a):
    msf = -MAX
    meh = 0
    st = en = be = 0
    for i in range(len(a)):
        meh+=a[i]
        if msf<meh:
            msf = meh
            st = be
            en = i
        if meh<0:
            meh = 0
            be = i+1
    return msf,st,en

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD



def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
for _ in range(int(input())):
    a,b,c = arrIN()
    print((a+b+c)//2)
    


for _ in range(int(input())):
    l=list(map(int,input().split()))
    a=sum(l)
    print(a//2)

import math


class Read:
    @staticmethod
    def int():
        return int(input())

    @staticmethod
    def list(sep=' '):
        return input().split(sep)

    @staticmethod
    def list_int(sep=' '):
        return list(map(int, input().split(sep)))


def solve():
    a, b, c = Read.list_int()
    print((a + b + c) // 2)


query_count = Read.int()
for j in range(query_count):
    solve()


#Anuneet Anand
q=int(input())
while q:
	a,b,c=list(map(int,input().split()))
	A=[a,b,c]
	print(sum(A)//2)
	q=q-1


import sys

t = int(input())
for i in range(t):
    a, b, c = list(map(int, sys.stdin.readline().split()))
    print((a+b+c)//2)


q = int(input())
for _ in range(q):
    a,b,c = list(map(int,input().split()))
    sum = a+b+c
    print(sum//2)


for i in range(int(input())):
    a, b, c = list(map(int, input().split()))
    print((a + b + c) // 2)


t = int(input())
for _ in range(t):
    a = list(map(int,input().split()))
    s = sum(a)
    print(s//2)