시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
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.
1 2 2 0 1 1 0
-1
1 6 6 2 0 2 1 0 3 4 3 1 4 3 5
4
1 6 10 0 0 5 0 5 0 4 9 9 9 9 9
36