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?

Input

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.

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.

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 \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$$$.

Exact Change

Examples