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

// 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);
    }
  }
}
