D. Без сдачи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды, рано утром, вы решили сходить в магазин неподалеку и купить там пачку чипсов. В магазине продаются чипсы $$$n$$$ разных вкусов. Пачка чипсов с $$$i$$$-м вкусом стоит $$$a_i$$$ бурлей.

В магазине могут закончиться чипсы каких-то вкусов, а потому вы решили выбрать пачку уже после того как придете в магазин. Однако у данного плана есть две серьезные проблемы:

  1. у вас есть только монеты номиналом $$$1$$$, $$$2$$$ и $$$3$$$ бурля;
  2. так как еще утро, в магазине вас попросят заплатить без сдачи, т. е. если вы выберете пачку чипсов с $$$i$$$-м вкусом, вы должны будете заплатить ровно $$$a_i$$$ бурлей.

Носить много монет тяжело, а потому вам хочется взять наименьшее суммарное количество монет. Соответственно, вас интересует вопрос: какое наименьшее количество монет вам нужно будет взять с собой, чтобы вы могли расплатиться за пачку чипсов любого вкуса без сдачи?

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество вкусов чипсов в магазине.

Во второй строке каждого запроса заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — стоимости пачек с соответствующими вкусами.

Выходные данные

Для каждого набора входных данных выведите одно число — наименьшее количество монет, которое вам понадобится взять с собой, чтобы купить пачку чипсов любого вкуса без сдачи.

Пример
Входные данные
4
1
1337
3
10 8 10
5
1 2 3 4 5
3
7 77 777
Выходные данные
446
4
3
260
Примечание

В первом наборе входных данных, вы можете, например, взять с собой $$$445$$$ монеты с номиналом $$$3$$$ и $$$1$$$ монету номинала $$$2$$$. Таким образом, вы наберете $$$1337 = 445 \cdot 3 + 1 \cdot 2$$$.

Во втором наборе, вы можете, например, взять $$$2$$$ монеты номинала $$$3$$$ и $$$2$$$ монеты номинала $$$2$$$. Так вы сможете заплатить как ровно $$$8 = 2 \cdot 3 + 1 \cdot 2$$$, так и ровно $$$10 = 2 \cdot 3 + 2 \cdot 2$$$.

В третьем наборе, достаточно взять $$$1$$$ монету номинала $$$3$$$ и $$$2$$$ монеты номинала $$$1$$$.