#P18840. [Croatian CPC2021] Cjelobrojne crte

[Croatian CPC2021] Cjelobrojne crte

Cjelobrojne crte

题目描述

Malnar 做了一张披萨,上面有 nn 个辣椒,第 ii 个辣椒的坐标为 (xi,yi)(x_i,y_i)。可以把披萨看作左下角为 (0,0)(0,0)、右上角为 (m,m)(m,m) 的正方形。他希望和朋友 Ivan 平分这张披萨。

他要沿一条直线切开披萨。若一条直线可以写成 y=ax+by=ax+b,其中 a,ba,b 都是整数,就称其为整数直线。

请计算满足以下两个条件的整数直线的数量:

  • 直线不经过任何一个辣椒;
  • 直线两侧的辣椒数量相同。

辣椒的坐标可以重复,重复的辣椒也分别计数。如果满足条件的直线有无穷多条,输出 −1-1。

输入格式

第一行包含一个整数 TT,表示测试用例数量。

每个测试用例的第一行包含两个整数 n,mn,m。接下来 nn 行,每行包含两个整数 xi,yix_i,y_i。

输出格式

对每个测试用例输出一行,包含满足条件的直线数量;若有无穷多条,则输出 −1-1。

数据范围

  • 1≤T≤1041\le T\le 10^4;
  • 2≤n≤1062\le n\le 10^6,且 nn 为偶数;
  • 1≤m≤1051\le m\le 10^5;
  • 0≤xi,yi<m0\le x_i,y_i<m;
  • 所有测试用例的 nn 之和不超过 10610^6,mm 之和不超过 10510^5。

样例 1

输入

1
2 2
0 1
1 0

输出

-1

样例 2

输入

1
6 6
2 0
2 1
0 3
4 3
1 4
3 5

输出

4

样例 3

输入

1
6 10
0 0
5 0
5 0
4 9
9 9
9 9

输出

36