题目描述

在物理实验室中，Alice 正在研究力的平衡问题。

实验室配备了 $k$ 种力发生器，第 $i$ 种发生器可以产生力向量 （$F_{x_i}, F_{y_i}$） 牛顿。其中，正值表示向右/向上的力，负值表示向左/向下的力。

为了达到完美的力学平衡状态，Alice 需要选择若干个力发生器（每种可以使用任意多次），使得所有力的合力恰好为零向量 （$0, 0$）。

由于实验经费有限，每次启动力发生器都需要消耗电能。Alice 希望启动力发生器的次数尽量少来达到平衡。

注意：Alice 必须至少启动一次力发生器，即答案至少为 $1$。

请帮助 Alice 计算最少需要启动多少次力发生器。如果无论如何都无法达到平衡，输出 $-1$。

输入格式

第一行一个整数 $t$，表示测试数据的组数。

对于每组测试数据：

• 第一行一个整数 $k$，表示力发生器的种类数。
• 接下来 $k$ 行，每行两个整数 $F_{x_i}, F_{y_i}$，表示第 $i$ 种力发生器产生的力向量。

对于所有测试数据：

• $1 \le t \le 10$
• $1 \le k \le 500$
• $-100 \le F_{x_i}, F_{y_i} \le 100$
• 保证 $\sum k \le 1000$

输出格式

对于每组测试数据，输出一行一个整数，表示最少需要启动的力发生器次数。如果无法达到平衡，输出 $-1$。

5
3
1 0
0 1
-1 -1
2
1 2
2 4
2
1 1
-2 -2
3
2 3
-1 4
3 -7
1
0 0

3
-1
3
-1
1