Exact Change
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:   you have only coins of $$$1$$$, $$$2$$$ and $$$3$$$ burles;  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?
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 \cdot 3 + 1 \cdot 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 \cdot 3 + 1 \cdot 2$$$ or $$$10 = 2 \cdot 3 + 2 \cdot 2$$$.In the third test case, it's enough to take $$$1$$$ coin of value $$$3$$$ and $$$2$$$ coins of value $$$1$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.The first line of each test case contains the single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of flavors in the store.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the cost of one bag of each flavor.
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.
import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    MAX = l[-1]
    ans = MAX // 3 + (MAX % 3 != 0)
    modset = list(set(list(map(lambda x: x % 3, l))))
    if MAX % 3 == 0:
        if len(modset) > 1:
            ans += 1
    elif MAX % 3 == 2:
        if 1 in modset:
            ans += 1
    elif 2 in modset:
        if l[0] == 1 or (n >= 2 and MAX - 1 in l):
            ans += 1
    print(ans)
t = int(input())
for _ in range(t):
    n = int(input())
    prices = list(map(int, input().split()))
    prices.sort()
    MAX = prices[-1]
    ans = MAX // 3
    if MAX % 3 != 0:
        ans += 1
    modset = set([p % 3 for p in prices])
    if MAX % 3 == 0:
        if len(modset) > 1:
            ans += 1
    elif MAX % 3 == 2:
        if 1 in modset:
            ans += 1
    elif 2 in modset and (prices[0] == 1 or MAX - 1 in prices):
        ans += 1
    print(ans)
ans = []
for p in range(int(input())):
    cnt = 0
    price = []
    u = int(input())
    mas = input().split()
    for i in range(u):
        mas[i] = int(mas[i])
    ost1 = 0
    ost2 = 0
    for i in mas:
        if i % 3 == 1:
            ost1 = 1
            if ost2 == 1:
                break
        if i % 3 == 2:
            ost2 = 1
            if ost1 == 1:
                break
    if 1 in mas:
        if max(mas) == 2:
            cnt = 2
        else:
            cnt = max(mas) // 3 + ost1 + ost2
            if max(mas) % 3 == 0 and ost2 == 1:
                cnt -= 1
    elif max(mas) == 2:
        cnt = 1
    elif max(mas) == 4:
        cnt = 2
        if 3 in mas and 2 in mas:
            cnt += 1
    else:
        cnt = max(mas) // 3 + ost1 + ost2
        if ost1 + ost2 == 2 and max(mas) % 3 == 1 and (not max(mas) - 1 in mas) or (ost1 + ost2 == 2 and max(mas) % 3 == 0):
            cnt -= 1
    ans.append(cnt)
for i in ans:
    print(i)