题目描述

Dasha 非常喜欢豚鼠。为此，她决定在家里养尽可能多的豚鼠，并制定了接下来 $n$ 天的计划。每天，她要么会买一只新的豚鼠，要么会请医生来检查她所有的宠物。

不幸的是，她打算买豚鼠的商店并不了解豚鼠，因此无法判断它们的性别。Dasha 也无法判断。唯一能帮忙的是医生。

豚鼠需要住在笼子里。Dasha 计划在同一家商店购买笼子。不幸的是，那里只出售一种笼子——双人笼。每个笼子最多只能住两只豚鼠。

由于 Dasha 不想让她的宠物受到心理伤害——她不会让两只不同性别的豚鼠住在同一个笼子里。

请你帮 Dasha 计算，在最坏情况下，她需要买多少个笼子，才能确保在任何时刻都不会有两只不同性别的豚鼠住在同一个笼子里。

在本题中，我们认为豚鼠只有两种性别——雄性和雌性。

输入格式

输入的第一行包含一个整数 $t$（$1 \leqslant t \leqslant 10^5$）——数据组数。

每组数据的第一行包含一个整数 $n$（$1 \leqslant n \leqslant 10^5$）——Dasha 的计划天数。

接下来一行包含 $n$ 个数字 $b_1, b_2, b_3, \ldots, b_n$（$1 \leqslant b_i \leqslant 2$）——Dasha 的计划。如果 $b_i = 1$，表示第 $i$ 天 Dasha 会买一只新的豚鼠。如果 $b_i = 2$，表示第 $i$ 天医生会来帮 Dasha 判断她已有的所有豚鼠的性别。

保证所有数据组的 $n$ 之和不超过 $10^5$。

输出格式

对于每组输入数据，输出一个整数——Dasha 至少需要买多少个笼子，才能确保无论豚鼠的性别如何，都可以让它们在任何时刻都不会有两只不同性别的豚鼠住在同一个笼子里。

说明/提示

在第一组输入数据中，Dasha 需要把每只豚鼠单独放在一个笼子里，因为她不知道它们的性别。

在第二组输入数据中，Dasha 一只豚鼠都不会买，因此她需要的笼子数量为 $0$。

在第三组输入数据中，在医生到来前的第 $4$ 天，Dasha 需要 $3$ 个笼子把每只豚鼠单独安置。当医生到来后，至少有两只豚鼠性别相同，可以合住一个笼子，第三只单独住。这样她会有一个空余的笼子，可以再安置一只新豚鼠。所以答案是 $3$。

在第四组输入数据中，答案为 $4$ 是最优的。

首先，前四只豚鼠可以各自单独放在一个笼子里。然后医生来判断它们的性别。在这四只豚鼠中，至少有一对性别相同，因为：要么雄性豚鼠至少有 $2$ 只，要么雄性不超过 $1$ 只，也就是说雌性至少有 $3$ 只。现在我们可以把这对豚鼠放在一个笼子里，另外两只分别单独放。这样我们就有一个空余的笼子，可以再安置一只新豚鼠。

现在说明答案至少为 $4$。假设前 $4$ 只豚鼠中有 $3$ 只是雌性，$1$ 只是雄性。我们至少需要 $3$ 个笼子来安置它们。然后当我们再买一只新豚鼠时，由于我们不知道它的性别，还需要再买一个笼子来安置它。

由 ChatGPT 4.1 翻译

样例

6
3
1 1 1
3
2 2 2
5
1 1 1 2 1
10
1 2 1 2 1 2 1 2 1 2
20
1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1
20
2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2

3
0
3
4
12
9