SP293 OFBEAT - Officers on the Beat

中世纪时期，比特兰的首都被坚固的城墙包围，以防止入侵者。城门有严密的守卫，夜间吊桥会被拉起，因此市民们感到十分安全。这样的安宁持续了一段时间。 但随着时间推移，围墙城市的弊端逐渐显现。人口的增长导致居住空间狭小，犯罪活动也日益猖獗。局势愈发糟糕，市长因此决定采取措施。一些原本驻扎在城门附近只负责看报的守卫被重新分派任务，要求他们在市内巡逻。许多警官对这个变化很不满，尤其是当第一批巡逻队员带着伤返回时，士气更为低落。意识到士气问题后，一位聪明的卫队长决定灵活执行市长的命令。他决定巡逻人员必须成群结队，身披重甲，只沿几条精挑细选的街道行动，从那里可以观察整个城市，而不需要实际介入事件。 城市以规则的网格布局，每条街道都从北到南或从东到西延伸，直达城墙。整数坐标的每个点都是南北向与东西向两条街道的交汇点。环绕城市的城墙形成一个简单的多边形，其边界直接位于城市某些街道的部分。 卫队长选择的“巡逻街道”集合中，任意一条街道都与其他至少一条巡逻街道相交。而且，对于城市里任意一点，必然可以从某条被巡逻的街道上的某个点看到（两点互相可见当且仅当连接它们的线段是整条街道的一部分）。最终，卫队长选择的巡逻街道集合是最少数量的。 根据比特兰首都的描述，确定卫队长下达命令后，实际上有多少条街道被巡逻。

第一行输入一个整数 $t$，表示测试用例的数量。接下来有 $t$ 个测试用例。 每个测试用例的第一行包含一个整数 $n$，表示城墙由多少段构成（$4 \le n \le 2000$）。第二行包含 $n$ 个整数 $a_1, \ldots, a_n$，描述连续的城墙段（$1 \le |a_i| \le 100000$）。任何连续的两段城墙都是互相垂直的。第 $i$ 段的长度为 $|a_i|$ 的值，而方向取决于 $a_i$ 的符号（正值表示向北或向东，负值表示向南或向西，按顺时针遍历城墙）。

对于每个测试用例，输出一个整数 $k$，代表卫队长选定的巡逻街道的数量。 **本翻译由 AI 自动生成**