description: 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.
solution: // package c1620;
  
  import java.io.File;
  import java.lang.invoke.MethodHandles;
  import java.util.Random;
  import java.util.Scanner;
  
  //
  // Educational Codeforces Round 119 (Rated for Div. 2) 2021-12-18 07:35
  // D. Exact Change
  // https://codeforces.com/contest/1620/problem/D
  // time limit per test 2 seconds; memory limit per test 256 megabytes
  // public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
  //
  // 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 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.
  //
  public class C1620D {
    static final int MOD = (int)1e9+7;
    static final Random RAND = new Random();
  
    static int solve(int[] a) {
      // value  coins
      //     1  1
      //     2  2
      //     3  3
      //     4  2,2 or 3,1
      //     5  3,2 or 3,1,1
      //     6  3,3 or 3,2,1
      //     7  3,3,1 or 3,2,2 or 3,2,1,1
      //     8  3,3,2 or 3,2,2,1
      // We want at most 1 one and at most 2 two
      int min3 = 0;
      for (int v : a) {
        if (v >= 6) {
          min3 = Math.max(min3, (v - 6) / 3);
        }
      }
  
      int ans = Integer.MAX_VALUE;
      for (int i = min3; i <= min3 + 2; i++) {
        for (int j = 0; j <= 3; j++) {
          for (int k = 0; k <= 3; k++) {
            boolean ok = true;
            for (int value : a) {
              if (!isOk(value, i, j, k)) {
                // System.out.format("  value:%3d i:%3d j:%3d k:%3d bad\n", value, i, j, k);
                ok = false;
                break;
              }
            }
            if (ok) {
              ans = Math.min(ans, i + j + k);
            }
          }
        }
      }
      return ans;
    }
  
    // Two whether coins (i,j,k) can make value v where i,j,k is the count for coin 3,2,1 respectively
    // Since (1,1,1) can makes all value in [0,6], we claim that i <= 3, j <= 3.
    static boolean isOk(int v, int i, int j, int k) {
      // System.out.format("  enter v:%2d i:%3d j:%3d k:%3d\n", v, i, j, k);
      int max = 3 * i + 2 * j + k;
      if (max < v) {
        return false;
      }
      if (max == v) {
        return true;
      }
  
      if (v == 0 || k >= v) {
        return true;
      } else if (v == 1) {
        return k > 0;
      } else if (v == 2) {
        // 2
        return j >= 1;
      } else if (v == 3) {
        // 3
        // 2 1
        return i >= 1 || (j >= 1 && k >= 1);
      } else if (v == 4) {
        // 3 1
        // 2 2
        // 2 1 1
        return (i >= 1 && k >= 1) || (j >= 2) || (j >= 1 && k >= 2);
      } else if (v == 5) {
        // 3 2
        // 3 1 1
        // 2 2 1
        // 2 1 1 1
        return (i >= 1 && j >= 1) || (i >= 1 && k >= 2) || (j >= 2 && k >= 1) || (j >= 1  && k >= 3);
      } else if (v == 6) {
        // 3 3
        // 3 2 1
        // 3 1 1 1 1
        // 2 2 2
        // 2 2 1 1
        // 2 1 1 1 1
        return (i >= 2) || (i >= 1 && j >= 1 && k >= 1) || (i >= 1 && k >= 4)
            || (j >= 3) || (j >= 2 && k >= 2) || (j >= 1 && k >= 4);
      } else {
        for (int h = 2; h >= 0; h--) {
          int m = v / 3 - h;
          if (m > 0 && m <= i && isOk(v - m * 3, i - m, j, k)) {
            return true;
          }
        }
        return false;
      }
    }
  
    // Get minimal additional number of coins to make v given one 1 and two 2 already available.
    // Possible values of one and two:
    //   one: {0,1}
    //   two: {0,1,2}
    //
    static int func(int v, int one, int two) {
      if (v == 0) {
        return 0;
      } else if (v == 1) {
        return one == 0 ? 1 : 0;
      } else if (v == 2) {
        return two == 0 ? 1 : 0;
      } else if (v == 3) {
        return (one == 1 && two > 0) ? 0 : 1;
      } else if (v == 4) {
        if (two == 2) {
          return 0;
        } else if (two == 1) {
          return 1;  // an additional 2 or 3
        } else {
          return one == 1 ? 1 : 2;
        }
      } else if (v == 5) {
        if (one == 1 && two == 2) {
          return 0;
        }
        return 1 + func(2, one, two);
      } else {
        int r = v % 3;
        return Math.min(v/3 + func(r, one, two), v/3 - 1 + func(3 + r, one, two));
      }
    }
  
    public static void main(String[] args) {
      Scanner in = getInputScanner();
      int T = in.nextInt();
      for (int t = 1; t <= T; t++) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
          a[i] = in.nextInt();
        }
        int ans = solve(a);
        System.out.println(ans);
      }
      in.close();
    }
  
    static Scanner getInputScanner() {
      try {
        final String USERDIR = System.getProperty("user.dir");
        final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
        final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
        return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
      } catch (Exception e) {
        return new Scanner(System.in);
      }
    }
  }
  