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.
//package learning;
import java.util.*;
import java.io.*;
import java.lang.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class NitsLocal {
    static ArrayList<String> s1;
    static boolean[] prime;
    static int n = (int)1e7;
    
     static void sieve() {
Arrays.fill(prime	, true);
prime[0] = prime[1] = false;
for(int i = 2 ; i * i <= n ; ++i) {
if(prime[i]) {
for(int k = i * i; k<= n ; k+=i) {
prime[k] = false;
}
}
}
 
}
    public static void main(String[] args) {
        InputReader sc = new InputReader(System.in);
        
           prime  = new boolean[n + 1];
           //sieve();
                prime[1] = false;
                /*
              int n = sc.ni();     
              int []a = sc.nia(n);
              int mod = 1000000007;
              long ans = 0;
              int f = 0;
              int q = sc.ni();
              while(q-- > 0)
              {
                  int num = sc.ni();
                  ans = 0;
                  if(num == 0)
                  {
                      a[sc.ni()-1] = sc.ni();
                  }
                 else
                  {
                      int l = sc.ni();
                      int r = sc.ni();
                    for(int i=l-1;i<r;i++)
                   {
                  
                   for(int j=i+1;j<r;j++)
                   {
                      f = 0;
                   
                      int x = a[i];
                      int y = a[j];
                      while(x > 0 && y > 0)
                      {
                          int y1 = x%10;
                          int y2 = y%10;
                          if(y1 > 0 && y2 > 0)
                          {
                              f = 1;
                          }
                          x /= 10;
                          y /= 10;
                      }
                      
                    
                    
                   
                     if(f==0)
                     {
                         ans = (ans + ((((long)a[i]%mod) * ((long)a[j]%mod)))%mod)%mod;
                     }
                  }
              }
              
              w.println(ans);
                  }
              }
          
            */
                /*
               int t  = sc.ni();
               while(t-- > 0)
               {
                   int n = sc.ni();
                   Student []st = new Student[n];
                   for(int i=0;i<n;i++)
                   {
                       st[i] = new Student(sc.ni(),sc.ni());
                   }
                   Arrays.sort(st,(p,q)->p.id-q.id);
                   if(n==1)
                       w.println("0");
                   else
                   {
                    int prev = 0;
                    int adv = 0;
                    int max = -1;
                    int min = 1000000000;
                    for(int i=0;i<n;i++)
                    {
                        min = Math.min(st[i].y,min);
                        max = Math.max(st[i].y,max);
                    }
                        if(st[0].y > st[1].y)
                        {
                            prev = st[0].id;
                        }
                        else
                            prev= st[0].y;
                         if(st[n-1].id < st[n-2].y)
                        {
                            adv = st[n-1].id;
                        }
                        else
                            prev= st[n-1].y;
                         w.println(adv-prev);
                    
                   }
               }
             */
               
                    int t = sc.ni();
                    while(t-- > 0)
                    {
                        int []a = new int[3];
                        for(int i=0;i<3;i++)
                        {
                            a[i] = sc.ni();
                        }
                        Arrays.sort(a);
                        int diff = a[2]-a[1];
                        a[2] = a[1];
                        int res = 0;
                        if(diff >= a[0])
                        {
                            res = a[0];
                            a[2] += (diff-a[0]);
                            res += Math.min(a[2], a[1]);
                            
                        }
                        else
                        {
                            res = diff;
                            a[0] -= diff;
                            a[1] += (a[0]/2);
                            a[2] += ((a[0]/2) + (a[0]%2));
                            res += Math.min(a[2], a[1]);
                            
                        }
                        
                        w.println(res);
                      
                       
                       
                    }
                      
                
                 
               
                
        
      
       w.close();
       
        
    }
    public static int upperBound(int []arr,int n,int num)
    {
        int l = 0;
        int r = n;
        while(l < r)
        {
            int mid = (l+r)/2;
            if(num >= arr[mid])
            {
                l = mid +1;
            }
            else
                r = mid;
        }
        return l;
    }
    public static int countSetBits(int number){
        int count = 0;
        while(number>0){
            ++count;
            number &= number-1;
        }
        return count;
    }
    
     static  class CustomerSortingComparator 
                                implements Comparator<Temp> {
 
    @Override
    public int compare(Temp cust1, Temp cust2) {
 
        // all comparison
        int compareName = 0;
        if(cust1.a < cust2.a)
            return 1;
        
        else if(cust1.a > cust2.a)
        return -1;
        else
        {
            if(cust1.b < cust2.b)
                return 1;
            else
                return -1;
            
        }
       
        }
    
    }
      

    public static long pow(long i, long j) {
		long res=1L;
		for(int a=0;a<j;a++) res*=i;
		return res;
	}
    public static long powmod(long i, long j,long MOD) {
		if(j==0) return 1L;
		if(j%2==0) {
			long temp=powmod(i,j/2,MOD);
			return (temp*temp)%MOD;
		}
		return (i*powmod(i,j-1,MOD))%MOD;
	}
    static HashSet<Integer> fac;
    public static void primeFactors(int n) 
    { 
        // Print the number of 2s that divide n 
        int t = 0;
        while (n%2==0) 
        { 
            fac.add(2);
            n /= 2; 
        } 
  
        // n must be odd at this point.  So we can 
        // skip one element (Note i = i +2) 
        for (int i = 3; i*i <= n; i+= 2) 
        { 
            // While i divides n, print i and divide n 
            while (n%i == 0) 
            { 
                fac.add(i);
                n /= i; 
            } 
        } 
  
        // This condition is to handle the case whien 
        // n is a prime number greater than 2 
        if (n > 2) 
            fac.add(n);
    } 
     static long modexp(long x,long n,long M)
{
    long power = n;
    long result=1;
    x = x%M;
    while(power>0)
    {
        if(power % 2 ==1)
            result=(result * x)%M;
        x=(x*x)%M;
        power = power/2;
    }
    return result;
}
    static long gcd(long a,long b)
    {
        if(a==0)
            return b;
        else
            return gcd(b%a,a);
    }
    static class Temp{
        int a;
        int b;
        int c;
        int d;
      
        Temp(int a,int b,int c,int d)
        {
            this.a = a;
            this.b = b;
            this.c  =c;
            this.d = d;
            //this.d = d;
        }
    }
    static class Query{
        int p;
        int index;
        int value;
        public Query(int p,int index,int value)
        {
            this.p = p;
            this.index = index;
            this.value = value;
            
        }
    }
    static int nextPowerOf2(int n) 
    { 
        int count = 0; 
  
        // First n in the below  
        // condition is for the  
        // case where n is 0 
        if (n > 0 && (n & (n - 1)) == 0) 
            return n; 
  
        while(n != 0) 
        { 
            n >>= 1; 
            count += 1; 
        } 
  
        return 1 << count; 
    } 
    
   static long sum1(int t1,int t2,int x,int []t)
   {
       int mid = (t2-t1+1)/2;
  if(t1==t2)
      return 0;
    
   else
   return sum1(t1,mid-1,x,t) + sum1(mid,t2,x,t);
    
     
   }
  
   
    static String replace(String s,int a,int n)
    {
        char []c = s.toCharArray();
        for(int i=1;i<n;i+=2)
        {
            int num = (int) (c[i] - 48);
            num += a;
            num%=10;
            c[i] = (char) (num+48);
        }
        return new String(c);
    }
    static String move(String s,int h,int n)
    {
        h%=n;
        char []c = s.toCharArray();
        char []temp = new char[n];
        for(int i=0;i<n;i++)
        {
            temp[(i+h)%n] = c[i];
        }
        return new String(temp);
    }
    
     public static int ip(String s){
return Integer.parseInt(s);
}
     static class multipliers implements Comparator<Long>{
  
         
  public int compare(Long a,Long b) {
   if(a<b)
    return 1;
   else if(b<a)
    return -1;
   else
    return 0;
  }
 }
     static class multipliers1 implements Comparator<Student>{
  
  public int compare(Student a,Student b) {
   if(a.y<b.y)
    return 1;
   else if(b.y<a.y)
    return -1;
   else
   {
       if(a.id < b.id)
           return 1;
       else if(b.id<a.id)
           return -1;
       else
           return 0;
           
    //return 0;
   }
  }
 }
    // Java program to generate power set in 
// lexicographic order. 
 
    
    
    
      static class InputReader {
 
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
 
public InputReader(InputStream st) {
this.stream = st;
}
 
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
 
public int ni() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
 
public long nl() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
 
public int[] nia(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = ni();
}
return a;
}
 
public String rs() {
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 String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
 
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
 
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
 
}
 
 
 
 
 
   
static PrintWriter w = new PrintWriter(System.out);
                  static class Student
    {
        int id;
        //int x;
       
        int y;
        //long z;
        
        Student(int id,int y)
        {
            this.id = id;
            //this.x = x;
            //this.s = s;
            this.y = y;
           // this.z = z;
            
            
            
           
        }
        
    }
}