Cjelobrojne crte

시간 제한5초메모리 제한1024 MB

요약

정수 직선 y = ax + b 중 어느 점도 지나지 않으면서 n개의 점을 정확히 반으로 나누는 직선의 개수를 구하고, 무한히 많으면 -1을 출력합니다.

난이도: 보통10점 중 7점
유형: 기하, 해시맵, 수학
정답자: 아직 제출이 없습니다

문제

Gospodin Malnar napravio je pizzu na kojoj se nalazi $n$ papričica, gdje su koordinate $i$ -te papričice $(x\_i , y\_i)$ . Pizzu možemo zamisliti kao kvadrat od točke $(0, 0)$ do točke $(m, m)$ . Sada bi htio podijeliti tu pizzu za svojim prijateljem Ivanom.

Gospodin Malnar će pizzu rezati po određenom pravcu. Dodatno, pravac smatra cjelobrojnim ako se može zapisati kao $y = ax + b$ gdje su $a$ i $b$ cijeli brojevi. Kako bi pravedno podijelio pizzu s Ivanom, potrebno je odabrati takav cjelobrojni pravac da je broj papričica s obje strane pravca jednak te naravno da pravac ne prolazi ni jednom papričicom.

Kako biste im pomogli, ispište koliko postoji takvih pravaca, odnosno $-1$ ako ih postoji beskonačno.

입력

U prvom retku je broj $T$ ( $1 ≤ T ≤ 10^4$ ). Slijedi $T$ test primjera.

U svakom od njih su u prvom retku brojevi $n$ i $m$ ( $2 ≤ n ≤ 10^6$ ), $n$ je paran, ( $1 ≤ m ≤ 10^5$ ). U sljedećih $n$ redaka su koordinate papričica $x\_i$ te $y\_i$ ( $0 ≤ x\_i , y\_i < m$ ).

Zbroj $n$ po svim test primjerima manji je ili jednak $10^6$ i zbroj $m$ po svim test primjerima manji je ili jednak $10^5$ .

출력

Potrebno je za svaki primjer ispisati broj takvih pravaca, odnosno $-1$ ako ih je beskonačno.

예제3

예제 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
```