A14856 | 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:

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?

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.