You have three piles of candies: red, green and blue candies:

  * the first pile contains only red candies and there are r candies in it, 
  * the second pile contains only green candies and there are g candies in it, 
  * the third pile contains only blue candies and there are b candies in it. 



Each day Tanya eats exactly two candies of different colors. She is free to choose the colors of eaten candies: the only restriction that she can't eat two candies of the same color in a day.

Find the maximal number of days Tanya can eat candies? Each day she needs to eat exactly two candies.

Input

The first line contains integer t (1 ≤ t ≤ 1000) — the number of test cases in the input. Then t test cases follow.

Each test case is given as a separate line of the input. It contains three integers r, g and b (1 ≤ r, g, b ≤ 10^8) — the number of red, green and blue candies, respectively.

Output

Print t integers: the i-th printed integer is the answer on the i-th test case in the input.

Example

Input


6
1 1 1
1 2 1
4 1 1
7 4 10
8 1 4
8 2 8


Output


1
2
2
10
5
9

Note

In the first example, Tanya can eat candies for one day only. She can eat any pair of candies this day because all of them have different colors.

In the second example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and green and blue candies on the second day.

In the third example, Tanya can eat candies for two days. For example, she can eat red and green candies on the first day, and red and blue candies on the second day. Note, that two red candies will remain uneaten.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Prac {	
	public static void main(String[] args) throws IOException {
		BufferInput in = new BufferInput();
		int t = in.nextInt();
		StringBuilder sb = new StringBuilder();
		while(t-->0) {
			int[] arr = in.nextIntArray(3);
			Arrays.sort(arr);
			if(arr[2]>=arr[0]+arr[1]) {
				sb.append(arr[1]+arr[0]).append("\n");
				continue;
			}
			else
	            sb.append((arr[0] + arr[1] + arr[2])/2).append("\n"); 
		}
		System.out.print(sb);
		
		
	}
static class BufferInput {
		final private int BUFFER_SIZE = 1 << 16;
		
		private DataInputStream din;
		
		private byte[] buffer;
		
		private int bufferPointer, bytesRead;
		
		public BufferInput() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
 
		public BufferInput(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
 
		/**
		 * Reads the input bytes until it encounters a new line char.
		 * @return
		 * @throws IOException
		 */
		public String readLine() throws IOException {
			byte[] buf = new byte[64];
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}
		
		/**
		 * 
		 * @return
		 * @throws IOException
		 */
		public String nextString() throws IOException{
			
			// Skip all whitespace characters from the stream
			byte c = read();
			while(Character.isWhitespace(c)){
				c = read();
			}
			
			StringBuilder builder = new StringBuilder();
			builder.append((char)c);
			c = read();
			while(!Character.isWhitespace(c)){
				builder.append((char)c);
				c = read();
			}
			
			return builder.toString();
		}
			
		/**
		 * Reads an integer value.
		 * @return
		 * @throws IOException
		 */
		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
 
			if (neg)
				return -ret;
			return ret;
		}
		
 
		/**
		 * Reads an array of integers.
		 * @return
		 * @throws IOException
		 */
		public int[] nextIntArray(int n) throws IOException {
			int arr[] = new int[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextInt();
			}
			return arr;
		}
 
 
		/**
		 * Reads a long value.
		 * @return
		 * @throws IOException
		 */
		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		
		
		/**
		 * Reads an array of long integers.
		 * @return
		 * @throws IOException
		 */
		public long[] nextLongArray(int n) throws IOException {
			long arr[] = new long[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextLong();
			}
			return arr;
		}
		
		/**
		 * 
		 * @return
		 * @throws IOException
		 */
		public char nextChar() throws IOException{
			byte c = read();
			while(Character.isWhitespace(c)){
				c = read();
			}
			return (char) c;	
		}
		
 
		/**
		 * Reads a double value.
		 * @return
		 * @throws IOException
		 */
		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
 
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
 
			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}
 
			if (neg)
				return -ret;
			return ret;
		}
 
		/**
		 * Reads an array of double values.
		 * @return
		 * @throws IOException
		 */
		public double[] nextDoubleArray(int n) throws IOException {
			double arr[] = new double[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextDouble();
			}
			return arr;
		}
		
		/**
		 * Fills the buffer from input stream.
		 * 
		 * @throws IOException
		 */
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
 
		/**
		 * 
		 * @return
		 * @throws IOException
		 */
		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}
 
		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}
 
}
 