One day, early in the morning, you decided to buy yourself a bag of chips in the nearby store. The store has chips of n different flavors. A bag of the i-th flavor costs a_i burles.

The store may run out of some flavors, so you'll decide which one to buy after arriving there. But there are two major flaws in this plan: 

  1. you have only coins of 1, 2 and 3 burles; 
  2. since it's morning, the store will ask you to pay in exact change, i. e. if you choose the i-th flavor, you'll have to pay exactly a_i burles. 



Coins are heavy, so you'd like to take the least possible number of coins in total. That's why you are wondering: what is the minimum total number of coins you should take with you, so you can buy a bag of chips of any flavor in exact change?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains the single integer n (1 ≤ n ≤ 100) — the number of flavors in the store.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the cost of one bag of each flavor.

Output

For each test case, print one integer — the minimum number of coins you need to buy one bag of any flavor you'll choose in exact change.

Example

Input


4
1
1337
3
10 8 10
5
1 2 3 4 5
3
7 77 777


Output


446
4
3
260

Note

In the first test case, you should, for example, take with you 445 coins of value 3 and 1 coin of value 2. So, 1337 = 445 ⋅ 3 + 1 ⋅ 2.

In the second test case, you should, for example, take 2 coins of value 3 and 2 coins of value 2. So you can pay either exactly 8 = 2 ⋅ 3 + 1 ⋅ 2 or 10 = 2 ⋅ 3 + 2 ⋅ 2.

In the third test case, it's enough to take 1 coin of value 3 and 2 coins of value 1.
1
1
6006

2002

import java.beans.DesignMode;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.CompletableFuture.AsynchronousCompletionTask;

import org.xml.sax.ErrorHandler;

import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.DataInputStream;

public class Solution {
        //TEMPLATE -------------------------------------------------------------------------------------
        public static boolean Local(){
            try{ 
                return System.getenv("LOCAL_SYS")!=null;
            }catch(Exception e){
                return false;
            }
        }   

        public static boolean LOCAL;

        static class FastScanner {

                BufferedReader br;
                StringTokenizer st ;

                FastScanner(){
                    br =  new BufferedReader(new InputStreamReader(System.in));
                    st = new StringTokenizer("");
                }

                FastScanner(String file) {

                    try{
                        br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
                        st = new StringTokenizer("");
                    }catch(FileNotFoundException e) {
                        // TODO Auto-generated catch block
                        System.out.println("file not found");
                        e.printStackTrace();
                    }
                    
                }
                String next() {
                    while (!st.hasMoreTokens())
                        try {
                            st = new StringTokenizer(br.readLine());
                        } catch (IOException e) {
                        }
                    return st.nextToken();
                }

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

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

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

                String readLine() throws IOException{
                    return br.readLine();
                }
            }
                                
        static class Pair<T,X> {

            T first;
            X second;
            
            Pair(T first,X second){
                this.first = first;
                this.second = second;
            }

            @Override
            public int hashCode(){
                return Objects.hash(first,second);
            }

            @Override
            public boolean equals(Object obj){
                return obj.hashCode() == this.hashCode();
            }

        }

    
    static PrintStream debug = null;      
    static long mod = (long)(Math.pow(10,9) + 7); 
//TEMPLATE -------------------------------------------------------------------------------------END//
    public static void main(String[] args) throws Exception {
        
        FastScanner s = new FastScanner();
        LOCAL = Local();
        //PrintWriter pw = new PrintWriter(System.out);
        if(LOCAL){
            s = new FastScanner("src/input.txt");
            
            PrintStream o = new PrintStream("src/sampleout.txt");
            debug = new PrintStream("src/debug.txt");
            System.setOut(o);
        //  pw = new PrintWriter(o);
        } long mod = 1000000007;

    
        int tcr = s.nextInt();                         
        StringBuilder sb = new StringBuilder();
    

        for(int tc=0;tc<tcr;tc++){
            int n = s.nextInt();
            int arr[] = new int[n];
            int max_3 = 0;
            int max_elem = 0;
            for(int i=0;i<n;i++){
                arr[i] = s.nextInt();
                max_elem = Math.max(arr[i],max_elem);
                max_3 = Math.max(max_3,arr[i]/3);
            }

            int ans = Integer.MAX_VALUE;

            for(int thr=max_3-4;thr<=max_3;thr++){
                for(int ones = 0;ones<=2;ones++){
                    for(int two = 0;two<=2;two++){
                        int total = ones + two + thr;
                        boolean poss = true;
                        for(int k=0;k<n;k++){
                            if(!poss(ones,two,thr,arr[k])){
                                poss = false;
                                break;
                            }
                        }

                        if(poss){
                            ans = Math.min(ans,total);
                        }
                    }
                }
            }

            sb.append(ans+"\n");



        }

        print(sb.toString());
    }

    public static boolean poss(int ones,int twos,int threes,int num){
        for(int i=0;i<=ones;i++){
            for(int j=0;j<=twos;j++){
                int val = num - (i*1) - (j*2);
                if(val < 0){continue;} 
                if(((val)%3 == 0) && ((val/3)<=threes)){
                    return true;
                }
            }
        }
        return false;
    }
    
    public static int next(int curr,int n){
        if(curr == n){
            return 1;
        }
        return curr + 1;
    }


    public static List<int[]> print_prime_factors(int n){
    
        List<int[]> list = new ArrayList<>();
        
        for(int i=2;i<=(int)(Math.sqrt(n));i++){

            if(n % i == 0){
                
                int cnt = 0;
                
                while( (n % i) == 0){
                    n = n/i;
                    cnt++;
                }

                list.add(new int[]{i,cnt});
            }
        }

        if(n!=1){
            list.add(new int[]{n,1});
        }

        return list;
    }

    public static List<int[]> prime_factors(int n,List<Integer> sieve){
        List<int[]> list = new ArrayList<>();
        int index = 0;
        while(n > 1 && sieve.get(index) <= Math.sqrt(n)){
            int curr = sieve.get(index);
            int cnt = 0;
            while((n % curr) == 0){
                n = n/curr;
                cnt++;
            }
            if(cnt >= 1){
                list.add(new int[]{curr,cnt});
            }
            index++;
        }
        if(n > 1){
            list.add(new int[]{n,1});
        }
        return list;
    }

    public static boolean inRange(int r1,int r2,int val){
        return ((val >= r1) && (val <= r2));
    }

    static int len(long num){
        return Long.toString(num).length();
    }

    static long mulmod(long a, long b,long mod)
    {
        long ans = 0l;
        
        while(b > 0){
            long curr = (b & 1l);
            if(curr == 1l){
                ans = ((ans % mod) + a) % mod;
            }
            
            a = (a + a) % mod;

            b = b >> 1;
        }

        return ans;
    }


    public static void dbg(PrintStream ps,Object... o) throws Exception{
        if(ps == null){
            return;
        }
        Debug.dbg(ps,o);
    }

    public static long modpow(long num,long pow,long mod){

        long val = num;
        long ans = 1l;

        while(pow > 0l){
            
            long bit = pow & 1l;

            if(bit == 1){
                ans = (ans * (val%mod))%mod;
            }

            val = (val * val) % mod;
            pow = pow >> 1;
        }

        return ans;

    }

    public static long pow(long num,long pow){

        long val = num;
        long ans = 1l;

        while(pow > 0l){
            
            long bit = pow & 1l;

            if(bit == 1){
                ans = (ans * (val));
            }

            val = (val * val);
            pow = pow >> 1;
        }

        return ans;
    }
    
    public static char get(int n){
        return (char)('a' + n);
    }

    public static long[] sort(long arr[]){
        List<Long> list = new ArrayList<>();
        for(long n : arr){list.add(n);}
        Collections.sort(list);
        for(int i=0;i<arr.length;i++){
            arr[i] = list.get(i);
        }
        return arr;
    }

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

    // return the (index + 1)
    // where index is the pos of just smaller element
    // i.e count of elemets strictly less than num
    public static int justSmaller(long arr[],long num){
        //  System.out.println(num+"@");
        int st = 0;
        int e = arr.length - 1;

        int ans = -1;

        while(st <= e){

            int mid = (st + e)/2;

            if(arr[mid] >= num){
                e = mid - 1;
            }else{
                ans = mid;
                st = mid + 1;
            }

        }


        return ans + 1;

    }
    public static int justSmaller(int arr[],int num){
        //  System.out.println(num+"@");
        int st = 0;
        int e = arr.length - 1;

        int ans = -1;

        while(st <= e){

            int mid = (st + e)/2;

            if(arr[mid] >= num){
                e = mid - 1;
            }else{
                ans = mid;
                st = mid + 1;
            }

        }


        return ans + 1;

    }
    
    //return (index of just greater element)
    //count of elements smaller than or equal to num

    public static int justGreater(long arr[],long num){
        int st = 0;
        int e = arr.length - 1;

        int ans = arr.length;

        while(st <= e){
            
            int mid = (st + e)/2;

            if(arr[mid] <= num){
                st = mid + 1;
            }else{
                ans = mid;
                e = mid - 1;
            }
        }

        return ans;

    }

    public static int justGreater(int arr[],int num){
        int st = 0;
        int e = arr.length - 1;

        int ans = arr.length;

        while(st <= e){
            
            int mid = (st + e)/2;

            if(arr[mid] <= num){
                st = mid + 1;
            }else{
                ans = mid;
                e = mid - 1;
            }
        }

        return ans;

    }

    

    public static void println(Object obj){
        System.out.println(obj.toString());
    }

    public static void print(Object obj){
        System.out.print(obj.toString());
    }

    public static int gcd(int a,int b){
        if(b == 0){return a;}
        return gcd(b,a%b);
    }

    public static long gcd(long a,long b){
        if(b == 0l){
            return a;
        }

        return gcd(b,a%b);
    }

    public static int find(int parent[],int v){
        if(parent[v] == v){
            return v;
        }
        
        return parent[v] = find(parent, parent[v]);
    }



    public static List<Integer> sieve(){
    
            List<Integer> prime = new ArrayList<>();

            int arr[] = new int[1000001];

        Arrays.fill(arr,1);

        arr[1] = 0;
        arr[2] = 1;

        for(int i=2;i<1000001;i++){
            
            if(arr[i] == 1){
                
                prime.add(i);

                for(long j = (i*1l*i);j<1000001;j+=i){
                    arr[(int)j] = 0;
                }
            }
        }

        return prime;
    }

    static boolean isPower(long n,long a){
        
        long log = (long)(Math.log(n)/Math.log(a));

        long power = (long)Math.pow(a,log);

        if(power == n){return true;}

        return false;
    }


    private static int mergeAndCount(int[] arr, int l,int m, int r)
    {
        // Left subarray
        int[] left =  Arrays.copyOfRange(arr, l, m + 1);

        // Right subarray
        int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

        int i = 0, j = 0, k = l, swaps = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j])
                arr[k++] = left[i++];
            else {
                arr[k++] = right[j++];
                swaps += (m + 1) - (l + i);
            }
        }
        while (i < left.length)
            arr[k++] = left[i++];
        while (j < right.length)
            arr[k++] = right[j++];
        return swaps;
    }

    // Merge sort function
    private static int mergeSortAndCount(int[] arr, int l,int r)
    {

        // Keeps track of the inversion count at a
        // particular node of the recursion tree
        int count = 0;

        if (l < r) {
            int m = (l + r) / 2;

            // Total inversion count = left subarray count
            // + right subarray count + merge count

            // Left subarray count
            count += mergeSortAndCount(arr, l, m);

            // Right subarray count
            count += mergeSortAndCount(arr, m + 1, r);

            // Merge count
            count += mergeAndCount(arr, l, m, r);
        }

        return count;
    }

    static class Debug{
        //change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
        public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;

        

        private static <T> String ts(T t) {
            if(t==null) {
                return "null";
            }
            try {
                return ts((Iterable<T>) t);
            }catch(ClassCastException e) {
                if(t instanceof int[]) {
                    String s = Arrays.toString((int[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}\n";
                }else if(t instanceof long[]) {
                    String s = Arrays.toString((long[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}\n";
                }else if(t instanceof char[]) {
                    String s = Arrays.toString((char[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}\n";
                }else if(t instanceof double[]) {
                    String s = Arrays.toString((double[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}\n";
                }else if(t instanceof boolean[]) {
                    String s = Arrays.toString((boolean[]) t);
                    return "{"+s.substring(1, s.length()-1)+"}\n";
                }
                try {
                    return ts((Object[]) t);
                }catch(ClassCastException e1) {
                    return t.toString();
                }
            }
        }
        private static <T> String ts(T[] arr) {
            StringBuilder ret = new StringBuilder();
            ret.append("{");
            boolean first = true;
            for(T t: arr) {
                if(!first) {
                    ret.append(", ");
                }
                first = false;
                ret.append(ts(t));
            }
            ret.append("}");
            return ret.toString();
        }
        private static <T> String ts(Iterable<T> iter) {
            StringBuilder ret = new StringBuilder();
            ret.append("{");
            boolean first = true;
            for(T t: iter) {
                if(!first) {
                    ret.append(", ");
                }
                first = false;
                ret.append(ts(t));
            }
            ret.append("}\n");
            return ret.toString();
        }
        public static void dbg(PrintStream ps,Object... o) throws Exception {
            if(LOCAL) {
                System.setErr(ps);
                System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [\n");
                for(int i = 0; i<o.length; i++) {
                    if(i!=0) {
                        System.err.print(", ");
                    }
                    System.err.print(ts(o[i]));
                }
                System.err.println("]");
            }
        }
    }

}