题目描述

在物理实验室中，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