该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

特别适合初学者，^_^

题目描述

在荒野深处，$Bileo$ 和 $Jily$ 发现了一系列蕴含抽象逻辑的聚集地。其中一些聚集地存在不一致的逻辑错误，随时可能崩溃。
他们希望通过合理的相邻传递安排，在相邻聚集地之间传递逻辑，使尽可能多的聚集地最终恢复逻辑稳定。

给定一个长度为 $n$ 的整数数组 $a$。

你可以进行任意次操作，每次操作如下：

选择一个下标 $i$，满足 $1 \leq i < n$，然后令：

每个下标最多只能被选择一次。

请你求出经过所有操作后，最终数组中正整数的最大数量。

格式

输入

每个测试点包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数

每组测试数据第一行包含一个整数 $n$，表示数组长度

第二行包含 $n$ 个整数：$a_1,a_2,\ldots,a_n$

保证所有测试数据中 $n$ 的总和不超过：$2 \cdot 10^5$

$1 \leq t \leq 10^4$

$2 \leq n \leq 2 \cdot 10^5$

$-10^9 \leq a_i \leq 10^9$

输出

对于每组测试数据，输出一行一个整数 $k$，表示最终数组中正整数数量的最大值。

样例

4
5
0 -1 3 -3 0
5
0 -2 1 2 3
5
0 1 0 1 0
2
1000000000 -1000000000

3
5
4
1

限制

1秒，512MiB，每个测试点。