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
import java.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * 
 * @author Saju
 *
 */

public class Main {

	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { -1, 0, 1, 0 };

	static final int MOD = 1000000007;

	public static void main(String[] args) {

		InputReader in = new InputReader(System.in);

		int q = in.nextInt();
		
		for(int i = 0; i < q; i++){
			String str1 = in.next();
			String str2 = in.next();
			String str3 = in.next();
			BigInteger big1 = new BigInteger(str1);
			BigInteger big2 = new BigInteger(str2);
			BigInteger big3 = new BigInteger(str3);
			
			BigInteger sum = big1.add(big2).add(big3);
			
			BigInteger div = sum.divide(BigInteger.valueOf(2));
			System.out.println(div);
		}

		System.exit(0);

	}

	static long determinantOfMatrix(long mat[][], int n) {
		long num1, num2, det = 1, total = 1; // Initialize result

		int index = 0;
		// temporary array for storing row
		long temp[] = new long[n + 1];

		// loop for traversing the diagonal elements
		for (int i = 0; i < n; i++) {
			index = i; // intialize the index

			// finding the index which has non zero value
			while (mat[index][i] == 0 && index < n) {
				index++;

			}
			if (index == n) // if there is non zero element
			{
				// the determinat of matrix as zero
				continue;

			}
			if (index != i) {
				// loop for swaping the diagonal element row and index row
				for (int j = 0; j < n; j++) {
					long tmp = mat[index][j];
					mat[index][j] = mat[i][j];
					mat[i][j] = tmp;
//					swap(mat[index][j], mat[i][j]);
				}
				// determinant sign changes when we shift rows
				// go through determinant properties
				det = ((long) (det * Math.pow(-1, index - i))) % MOD;
			}

			// storing the values of diagonal row elements
			for (int j = 0; j < n; j++) {
				temp[j] = mat[i][j];

			}
			// traversing every row below the diagonal element
			for (int j = i + 1; j < n; j++) {
				num1 = temp[i]; // value of diagonal element
				num2 = mat[j][i]; // value of next row element

				// traversing every column of row
				// and multiplying to every row
				for (int k = 0; k < n; k++) {
					// multiplying to make the diagonal
					// element and next row element equal
					mat[j][k] = (num1 * mat[j][k]) % MOD - (num2 * temp[k]) % MOD;

				}
				total = (total * num1) % MOD; // Det(kA)=kDet(A);
			}

		}

		// mulitplying the diagonal elements to get determinant
		for (int i = 0; i < n; i++) {
			det = (det * mat[i][i]) % MOD;

		}
		return (det / total) % MOD; // Det(kA)/k=Det(A);
	}

	public static long matrixDeterminant(long[][] matrix) {
		long temporary[][];
		long result = 0;

		if (matrix.length == 1) {
			result = matrix[0][0] % MOD;
			return (result);
		}

		if (matrix.length == 2) {
			result = ((matrix[0][0] * matrix[1][1]) % MOD - (matrix[0][1] * matrix[1][0]) % MOD);
			return (result) % MOD;
		}

		for (int i = 0; i < matrix[0].length; i++) {
			temporary = new long[matrix.length - 1][matrix[0].length - 1];

			for (int j = 1; j < matrix.length; j++) {
				for (int k = 0; k < matrix[0].length; k++) {
					if (k < i) {
						temporary[j - 1][k] = matrix[j][k];
					} else if (k > i) {
						temporary[j - 1][k - 1] = matrix[j][k];
					}
				}
			}

			long temp = (long) ((matrix[0][i] * Math.pow(-1, i) * matrixDeterminant(temporary)) % MOD);
			result = (result + temp) % MOD;
		}
		return (result) % MOD;
	}

	// O(log(max(A, B))).
	static long gcd(long a, long b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static void primeFactorization(int n) {
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				int count = 0;
				while (n % i == 0) {
					count++;
					n = n / i;
				}
				System.out.println("i: " + i + ", count: " + count);

			}

		}
		if (n != 1) {
			System.out.println(n);

		}
	}

	private static double getDistance(double x1, double y1, double x2, double y2) {

		return Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2);
	}

	private static int getDecimal(String str) {
		int val = 0;

		for (int i = str.length() - 1, j = 0; i >= 0; i--, j++) {
			if (str.charAt(i) == '1') {
				val += Math.pow(2, j);
			}
		}
		return val;
	}

	private static int call(int i, int j, int[][] colors) {

		if (i >= colors.length) {
			return 0;
		}

		if (dp[i][j] != -1) {
			return dp[i][j];

		}

		int result = Integer.MAX_VALUE;

		for (int k = 0; k < 3; k++) {
			if (k == j) {
				continue;
			} else {
				result = Math.min(result, call(i + 1, k, colors) + colors[i][j]);
			}
		}

		return dp[i][j] = result;
	}

	static int dp[][];

	private static class Graph {

		List<Edge> adjList[];
		int v;
		boolean visited[];
		int first[];
		int second[];

		Graph(int n) {
			this.v = n;
			adjList = new ArrayList[n];
			visited = new boolean[n];
			first = new int[n];
			second = new int[n];

			for (int i = 0; i < n; i++) {
				adjList[i] = new ArrayList<>();
			}
		}

		public void addEdge(int u, int v, int w) {
			adjList[u].add(new Edge(u, v, w));
			adjList[v].add(new Edge(v, u, w));
		}

		private void bfsAnother(int source) {
			Arrays.fill(visited, false);
			visited[source] = true;
			Queue<Integer> queue = new LinkedList<>();
			queue.add(source);
			second[source] = 0;

			while (!queue.isEmpty()) {
				int u = queue.remove();

				for (Edge e : adjList[u]) {
					if (!visited[e.v]) {
						queue.add(e.v);
						visited[e.v] = true;
						second[e.v] = second[u] + e.w;
					}
				}
			}
		}

		int firstFarthest;

		private void bfs(int source) {
			Arrays.fill(visited, false);
			visited[source] = true;
			Queue<Integer> queue = new LinkedList<>();
			queue.add(source);
			int max = 0;
			first[source] = 0;

			while (!queue.isEmpty()) {
				int u = queue.remove();
				if (first[u] > max) {
					max = first[u];
					firstFarthest = u;
				}
				for (Edge e : adjList[u]) {
					if (!visited[e.v]) {
						queue.add(e.v);
						visited[e.v] = true;
						first[e.v] = first[u] + e.w;
					}
				}
			}
		}

		public int dfs(int source) {

			visited[source] = true;
			int val = 0;
			int max = 0;
			for (Edge e : adjList[source]) {
				val = 0;
				if (!visited[e.v]) {
					val += (e.w + dfs(e.v));
				}
				max = Math.max(val, max);
			}

			return max;
		}
	}

	private static class Edge {
		int u;
		int v;
		int w;

		Edge(int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
	}

	private static BigInteger fac(int n, int mod) {

		if (n <= 0) {
			return BigInteger.ONE;
		}
		return BigInteger.valueOf(n).multiply(fac(n - 1, mod));
	}

	private static long bigMod(long n, long k, long m) {

		long ans = 1;
		while (k > 0) {
			if ((k & 1) == 1) {
				ans = (ans * n) % m;
			}
			n = (n * n) % m;
			k >>= 1;
		}
		return ans;
	}

	private static int upperBound(long[] arr, long num) {

		int start = 0;
		int end = arr.length;

		int mid = 0;
		int index = 0;
		while (true) {

			if (start > end) {
				break;
			}
			mid = (start + end) / 2;
			if (arr[mid] > num) {
				end = mid - 1;

			} else if (arr[mid] < num) {
				start = mid + 1;
			} else {
				return mid;
			}

		}

		// System.out.println(mid);
		if (arr[mid] < num) {
			index = mid + 1;
		} else {
			index = mid;
		}
		return index;
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(reader.readLine());

				}
			} catch (IOException e) {
				return null;
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			String line = null;
			try {
				tokenizer = null;
				line = reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			return line;
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public boolean hasNext() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(reader.readLine());
				}
			} catch (Exception e) {
				return false;
			}
			return true;
		}
	}
}