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

public class E1260 {
    public static void pri_result(int i) {
        System.out.println(i);
        System.exit(0);
    }

    public static void SolveA() {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] r = new int[t];
        int[] g = new int[t];
        int[] b = new int[t];
        for (int i = 0; i < t; i++) {
            r[i] = sc.nextInt();
            g[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }

        for (int i=0; i< t; i++) {
            int answer;
//            answer = Math.min( r[i] + g[i], b[i]);
//            answer = Math.max (answer, 
//                    Math.min(r[i] + b[i], g[i])
//            );
//            answer = Math.max (answer,
//                    Math.min(g[i] + b[i], r[i])
//                    );

            int a[] = new int[3];
            a[0] = r[i]; a[1] = g[i]; a[2] = b[i];
            Arrays.sort(a);
//            int answer1 = Math.min(a[0] + a[1], a[2]);           
//            answer = a[0];
//            if (a[0] % 2 == 1)
//                a[2] -= 1;
//            a[2] -= a[0]/2;
//            a[1] -= a[0]/2;
//            answer = a[0] + Math.min(a[1],a[2]);
            // make a[1] the same as a[2]
            if (a[0] + a[1] <= a[2]) {
                System.out.println(a[0] + a[1]);
            }
            else {
                a[0] -= a[2] - a[1];
                System.out.println(a[0]/2 + a[2]);
            }
            // System.out.println( Math.max(answer, answer1));
        }
        System.exit(0);
    }

    public static void SolveB() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] a = new int [n];
        int [] d = new int [n];
        int dc = 0;
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        boolean startD = true;
        Set employee   = new HashSet();
        Set employeeD  = new HashSet();
        int startN = 0;
        for (int i= 0; i < n; i++ ) {
            // move as much as I can
            startD = false;
            if (a[i] > 0 ) {
                if (employeeD.contains(a[i])) {
                    System.out.println(-1);
                    System.exit(0);
                }
                employee.add(a[i]);
                employeeD.add(a[i]);
            }
            else {
                int ea = -1 * a[i];
                if (employee.contains(ea)) {
                    employee.remove(ea);
                }
                else {
                    System.out.println(-1);
                    System.exit(0);                    
                }
            }
            if (employee.isEmpty()) {
                startD = true;
                d[dc ++] = i - startN + 1;
                startN = i +1;
                employeeD.clear();
            }
        }
        if (!employee.isEmpty()) {
            System.out.println(-1);
            
        }
        else {
            System.out.println(dc);
            for (int j=0; j< dc; j++) {
                System.out.print(d[j] + " ");
            }
            System.out.println();
        }
        System.exit(0);
    }

    public static void SolveC() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Integer [] a = new Integer [n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);

        int mc = 0;
        long total = 0L;
        long [] adds = new long [m];
        long [] ans  = new long [n];
        for (int i = 0; i < n; i++) {
            adds[mc] += a[i];
            total += adds[mc];
            ans[i] = total;
 
            mc++;
            if (mc >= m) {
                mc = 0;
            }
        }
        for (int i=0; i< n; i++)
            System.out.print(ans[i] + " ");
        System.out.println();
        System.exit(0);
    }

    public static void SolveC2() {
	PrintWriter out = new PrintWriter(System.out);        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Integer [] a = new Integer [n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);

        int mc = 0;
        long total = 0L;
        long [] adds = new long [m];
        long [] ans  = new long [n];
        for (int i = 0; i < n; i++) {
            adds[mc] += a[i];
            total += adds[mc];
            ans[i] = total;
 
            mc++;
            if (mc >= m) {
                mc = 0;
            }
        }
        for (int i=0; i< n; i++)
            out.print(ans[i] + " ");
        out.println();
        out.close();
        System.exit(0);
    }

    public static void D_aux(int i, int j) {
        int i1 = i + 1;
        int j1 = j + 1;
        pw.println(i1 + " " + j1);
    }

    static PrintWriter pw; 
    public static void SolveD() {
        Scanner sc = new Scanner(System.in);
        pw = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt();
        char[] l = new char[n];
        char[] r = new char[n];
        int[][] lc = new int[27][n + 1];
        int[][] rc = new int[27][n + 1];

        l = sc.next().toCharArray();
        r = sc.next().toCharArray();

        for (int i = 0; i < n; i++) {
            if (l[i] == '?') {
                lc[26][0]++;
                lc[26][lc[26][0]] = i;

            } else {
                int temp = l[i] - 'a';
                lc[temp][0]++;
                lc[temp][lc[temp][0]] = i;
            }

            if (r[i] == '?') {
                rc[26][0]++;
                rc[26][rc[26][0]] = i;

            } else {
                int temp = r[i] - 'a';
                rc[temp][0]++;
                rc[temp][rc[temp][0]] = i;
            }

        }
        int total_m = 0;
        for (int i = 0; i < 26; i++) {
            total_m += Math.min(lc[i][0], rc[i][0]);
        }

        total_m = Math.min(n, total_m + lc[26][0] + rc[26][0]);

        pw.println(total_m);

        int l26_i = 0;
        int r26_i = 0;

        for (int i = 0; i < 26; i++) {
            int j = 0;
            for (; j < lc[i][0] && j < rc[i][0]; j++) {
                D_aux(lc[i][j + 1], rc[i][j + 1]);
            }
            while (j < lc[i][0] && r26_i < rc[26][0]) {
                D_aux(lc[i][j + 1], rc[26][r26_i + 1]);
                j++;
                r26_i++;
            }
            while (j < rc[i][0] && l26_i < lc[26][0]) {
                D_aux(lc[26][l26_i + 1], rc[i][j + 1]);
                j++;
                l26_i++;
            }
        }

        while (l26_i < lc[26][0] && r26_i < rc[26][0]) {
            D_aux(lc[26][l26_i + 1], rc[26][r26_i + 1]);
            l26_i++;
            r26_i++;
        }
        pw.close();

    }

    static int find_i(long value, long[] d) {
        for (int i = 0; i < d.length; i++) {
            if (d[i] <= value) {
                return i + 1;
            }
        }
        return d.length;
    }

    public static void SolveE() {
        Scanner sc = new Scanner(System.in);
        long H = sc.nextLong();
        int n = sc.nextInt();
        int[] d = new int[n];
        long[] par_d = new long[n];
        long min_d = 0;

        for (int i = 0; i < n; i++) {
            d[i] = sc.nextInt();
            if (i == 0) {
                par_d[i] = d[i];
            } else {
                par_d[i] = d[i] + par_d[i - 1];
            }
            if (par_d[i] < min_d) {
                min_d = par_d[i];
            }
        }

        if (H + min_d > 0 && par_d[n - 1] >= 0) {
            pri_result(-1);
        }

        if (H + min_d <= 0) {  // Wrong test #12
            System.out.println(find_i(-1L * H, par_d));
            System.exit(0); // wrong answer on Test #4
        }

        long temp = (H + min_d) / (-1L * par_d[n - 1]);
        long H_temp = H + temp * par_d[n - 1];
        if (H_temp + min_d > 0) {
            temp++;
            H_temp += par_d[n - 1];
        }
        System.out.println(temp * n + find_i(-1L * H_temp, par_d));
    }

    public static void main(String args[]) {
        SolveA();
        // SolveB();
        // SolveC();
        // SolveC2();
        // SolveD();
        // SolveE();
    }    
}
