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 ≤ q ≤ 1000) — the number of queries. Then q queries follow.

The only line of the query contains three integers a, b and c (1 ≤ a, b, c ≤ 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
//package clipse;


import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;
import java.io.*;
import java.math.*;


public class C
{
	
	static StringBuilder sb;
	
	static boolean dp[][];
	static int cnt=0;
	
	
	
	static void solve()
	{
	long sum=0;
	for(int a:new int [] {0,1,2})
	sum+=l();
	System.out.println(sum/2);
	
		
		
		
	}
		
		
		
		
		
	
	

	 public static void main(String[] args)
	    {
		 
		 int p = 1000000007;
		 inverse obj=new inverse(100001);
		 obj.InverseofNumber(p);
		 obj.InverseofFactorial(p);
		 obj.factorial(p);
		 
		 int testcase=i();
		 		
	         sb=new StringBuilder();
	        int tmp=testcase;
	         while(testcase-->0)
	         {
	        	 
	        	 solve();
	         }
	         
	         System.out.println(sb);
	         
	    }
	 
	 
	 //*********************************Disjoint set union*************************//
	 static class dsu
	 {
		 int parent[];
		 int size[];
		 dsu(int n)
		 {
			 parent=new int[n];
			 size=new int[n];
			 Arrays.fill(size,-1);
			 for(int i=0;i<n;i++)
				 parent[i]=-1;
		 }
		 int find(int a)
		 {
			 if(parent[a]<0)
				 return a;
			 else
			 {
				 int x=find(parent[a]);
				 parent[a]=x;
				 return x;
			 }
		 }
		 void merge(int a,int b)
		 {
			 a=find(a);
			 b=find(b);
			 if(a==b)
				 return;
			 parent[b]=a;
			 size[a]+=size[b];
		 }
	 }
	 
	 
	 
//*******************************************PRIME FACTORIZE *****************************************************************************************************//
	 static TreeMap<Long,Long> prime(long n)
	 {
		 TreeMap<Long,Long>h=new TreeMap<>();
		 long num=n;
		 
		 for(int i=2;i<=Math.sqrt(num);i++)
		 {
			 if(n%i==0)
			 {
				 int nt=0;
				 while(n%i==0) {
					 n=n/i;
					 nt++;
				 }
				 h.put((long)i, (long)nt);
			 }
		 }
		 if(n!=1)
			 h.put((long)n, (long)1);
		 return h;
		 
	 }
	 
///////////////////////****************************************-----------------------------.........................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>***********************************************	
	 
	static long [] xsort(long A[])
	{
		ArrayList<Long>l=new ArrayList<>();
		for(long a:A)
			l.add(a);
		Collections.sort(l);
		for(int i=0;i<l.size();i++)
			A[i]=l.get(i);
		
			return A;
		
		
	}
	 
	
//*************CLASS PAIR ***********************************************************************************************************************************************
	static class pair implements Comparable<pair>
    {
        long x;
        int y;

        pair(long x, int y) {
            this.x = x;
            this.y = y;
        }
        public int compareTo(pair o)
        {
        	return (int)(x-o.x);
        	
        }
		
       
    }
//*************CLASS PAIR *****************************************************************************************************************************************************
	
	
	

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int Int() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String String() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return String();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void flush() {
            writer.flush();
        }
    }

    static InputReader in = new InputReader(System.in);
    static OutputWriter out = new OutputWriter(System.out);
    static int modulus = (int) 1e7;

    public static int[] sort(int[] a) {
        int n = a.length;
        ArrayList<Integer> l = new ArrayList<>();
        for (int i : a)
            l.add(i);
        Collections.sort(l);
        for (int i = 0; i < l.size(); i++)
            a[i] = l.get(i);
        return a;
    }

    public static long pow(long x, long y) {
        long res = 1;
        while (y > 0) {
            if (y % 2 != 0) {
                res = (res * x) % modulus;
                y--;

            }
            x = (x * x) % modulus;
            y = y / 2;
        }
        return res;
    }
//GCD___+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    public static long gcd(long x, long y) {
        if (x == 0)
            return y;
        else
            return gcd(y % x, x);
    }
    //****************LOWEST COMMON MULTIPLE   *************************************************************************************************************************************

    public static long lcm(long x, long y) {
        return (x * (y / gcd(x, y)));
    }
//INPUT PATTERN******************************************************************************************************************************************************************
    public static int i() {
        return in.Int();
    }

    public static long l() {
        String s = in.String();
        return Long.parseLong(s);
    }

    public static String s() {
        return in.String();
    }

    public static int[] readArray(int n) {
        int A[] = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = i();
        }
        return A;
    }

    public static long[] readArray(long n) {
        long A[] = new long[(int) n];
        for (int i = 0; i < n; i++) {
            A[i] = l();
        }
        return A;
    }

//////////////////////////************************************INVERSE MODULO******************************************************************
static class inverse 
{
	static int N;
	static long[] factorialNumInverse;
	static long[] naturalNumInverse;
	static long[] fact;
	inverse(int n)
	{
		this.N=n;
		
		 factorialNumInverse = new long[N + 1];
		 
	    // Array to precompute inverse of 1! to N!
	     naturalNumInverse = new long[N + 1];
	 
	    // Array to store factorial of first N numbers
	     fact = new long[N + 1];
	 
	}
	

// Function to precompute inverse of numbers
static void InverseofNumber(int p)
{
naturalNumInverse[0] = naturalNumInverse[1] = 1;

for(int i = 2; i <= N; i++)
    naturalNumInverse[i] = naturalNumInverse[p % i] *
            (long)(p - p / i) % p;
}

// Function to precompute inverse of factorials
static void InverseofFactorial(int p)
{
factorialNumInverse[0] = factorialNumInverse[1] = 1;

// Precompute inverse of natural numbers
for(int i = 2; i <= N; i++)
    factorialNumInverse[i] = (naturalNumInverse[i] *
            factorialNumInverse[i - 1]) % p;
}

// Function to calculate factorial of 1 to N
static void factorial(int p)
{
fact[0] = 1;

// Precompute factorials
for(int i = 1; i <= N; i++)
{
    fact[i] = (fact[i - 1] * (long)i) % p;
}
}

// Function to return nCr % p in O(1) time
static long comb(int N, int R, int p)
{

// n C r = n!*inverse(r!)*inverse((n-r)!)
long ans = ((fact[N] * factorialNumInverse[R]) %
        p * factorialNumInverse[N - R]) % p;

return ans;
}
}
//////////////////////////************************************INVERSE MODULO******************************************************************
}








	