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

Вы — начинающий режиссер, и вы только выпустили свой первый фильм. Вы также запустили простой сайт, на котором есть две кнопки — лайк и дизлайк.

Однако сайт не так прост внутри. Есть два сервера, на каждом из них лайки и дизлайки считаются независимо.

$$$n$$$ пользователей заходят на сайт один за другим. Каждый пользователь одного из следующих типов:

  • тип $$$1$$$: пользователь смотрел фильм, и он им понравился — они нажимают лайк;
  • тип $$$2$$$: пользователь смотрел фильм, и он им не понравился — они нажимают дизлайк;
  • тип $$$3$$$: пользователь не смотрел фильм — они смотрят на текущее количество лайков и дизлайков и решают на какую кнопку нажимать. Если больше дизлайков, чем лайков, то пользователь ставит дизлайк. Иначе, они ставят лайк.

Каждый пользователь оценивает фильм ровно один раз.

Так как у вас есть два сервера, можно манипулировать оценками, чтобы фильм получил как можно больше лайков. Когда пользователь заходит на сайт, вы знаете его тип, и можете решить, на какой из двух серверов его послать.

Какое наибольшее количество лайков можно собрать в сумме по двум серверам, если распределить пользователей по двум серверам?

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

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

Затем следуют описания $$$t$$$ наборов входных данных.

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

Во второй строке каждого набора входных данных записано $$$n$$$ целых чисел $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 3$$$) — типы пользователей в том же порядке, в котором они заходят на сайт.

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

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

Пример
Входные данные
4
1
2
3
1 2 3
5
1 1 1 1 1
3
3 3 2
Выходные данные
0
2
5
2
Примечание

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

Во втором наборе входных данных в примере можно послать всех пользователей на первый сервер:

  • первый пользователь ставит лайк;
  • второй пользователь ставит дизлайк;
  • последний пользователь видит, что количество дизлайков не превышает количество лайков — ставит лайк сам.

Всего в сумме два лайка. Вместо этого можно послать первого и второго пользователя на первый сервер, а последнего — на второй.

  • первый пользователь ставит лайк на первом сервере;
  • второй пользователь ставит дизлайк на первом сервере;
  • последний пользователь не видит лайков или дизлайков на втором сервере — ставит лайк сам.