human
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.
Using python3 can you solve the prior task?
 ... Can you provide a Python code to print one integer — the minimum number of coins you need to buy one bag of any flavor you'll choose in exact change?
assistant
#Here is Python code to print one integer — the minimum number of coins you need to buy one bag of any flavor you'll choose in exact change.

inf = 2000000000

def solve1(a, n, n1, n2): # return n1 + n2 + minN3 required
    ans = 0
    for x in a:
        minCntsForX = inf
        for nn1 in range(n1 + 1):
            for nn2 in range(n2 + 1):
                y = x - nn1 - nn2 * 2
                if y >= 0 and y % 3 == 0:
                    minCntsForX = min(minCntsForX, n1 + n2 + y // 3)
        ans = max(ans, minCntsForX)
    return ans
                
            

def solve(a, n):
    ans = inf
    for n1 in range(5):
        for n2 in range(5): # guess that all ans has max of 10 n1 and 10 n2
            ans = min(ans, solve1(a, n, n1, n2))
    return ans

def main():
    
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        allans.append(solve(a, n))
    multiLineArrayPrint(allans)
    
    return

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ansArr):
    print('! {}'.format(' '.join([str(x) for x in ansArr])))
    sys.stdout.flush()
 
inf=float('inf')
# MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
import math
# from math import floor,ceil # for Python2
 
for _abc in range(1):
...