시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1364 481 294 34.306%

문제

강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다.

작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 75000)이 주어진다. 다음 n개 줄에는 각 섬의 좌표 xi, yi가 주어진다. 두 섬의 좌표가 같은 경우는 없다. (-109 ≤ xi, yi ≤ 109)

출력

각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다.

예제 입력 1

2
4
-10 -10
-10 10
10 -10
10 10
3
1 3
2 2
3 1

예제 출력 1

5
3
W3sicHJvYmxlbV9pZCI6IjU0MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODFcdWMxMWNcdWQ0OGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxNVx1ZDU1YyBcdWJkODFcdWMxMWNcdWQ0OGRcdWM3NzQgXHViZDg4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjczYlx1Yzc0MCBcdWIzZDlcdWNhYmRcdWFjZmMgXHViMGE4XHVjYWJkIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1ZDU2ZFx1ZDU3NFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHViZDgxXHVjYWJkXHVjNzc0XHViMDk4IFx1YzExY1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWQ1NmRcdWQ1NzRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkxXHVjNzQwIFx1YzEyY1x1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1YjI5NCBcdWJjMTRcdWIyZTRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWMxMmNcdWM3NDAgXHVjODhjXHVkNDVjIFx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWQ1NWMgXHVjODEwXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiB5IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YmQ4MVx1Y2FiZCwgeFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQwIFx1YjNkOVx1Y2FiZFx1Yzc3NFx1YjJlNC4gXHViZDgxXHVjMTFjXHVkNDhkXHVjNzQ0IFx1ZDBjMFx1YWNlMCBcdWQ1NmRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMmNcdWM3NTggXHVjMzBkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzEyY1x1Yzc1OCBcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyA3NTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzEyY1x1Yzc1OCBcdWM4OGNcdWQ0NWMgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1YzEyY1x1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuICgtMTA8c3VwPjk8XC9zdXA+ICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViZDgxXHVjMTFjXHVkNDhkXHVjNzQ0IFx1ZDBjMFx1YWNlMCBcdWQ1NmRcdWQ1NzRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMmNcdWM3NTggXHVjMzBkXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5vcnRoLVdlc3Rlcm4gV2luZHMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgc3Ryb25nIE5vcnRoLVdlc3Rlcm4gd2luZCBpcyBibG93aW5nLiBXaGVuIHNhaWxpbmcgdGhpcyBtZWFucyB0aGF0IHlvdSBjYW4gc2FpbCB0byB0aGUgRWFzdCwgdG8gdGhlIFNvdXRoIG9yIHRvIGFueSBkaXJlY3Rpb24gYmV0d2VlbiBFYXN0IGFuZCBTb3V0aC4gSXQgaXMgaW1wb3NzaWJsZSB0byBnbyBlaXRoZXIgTm9ydGgtIG9yIFdlc3R3YXJkcy48XC9wPlxyXG5cclxuPHA+SW4gdGhlIG9jZWFuIHRoZXJlIGFyZSBhIGxhcmdlIG51bWJlciBvZiBzbWFsbCBpc2xhbmRzLiBUaGVzZSBpc2xhbmRzIGFyZSBkZXNjcmliZWQgYnkgY29vcmRpbmF0ZSBwYWlycyAoeCwgeSkgb24gYSBncmlkLiBUaGUgcG9zaXRpdmUgeS1kaXJlY3Rpb24gaXMgTm9ydGh3YXJkcyBhbmQgdGhlIHBvc2l0aXZlIHgtZGlyZWN0aW9uIGlzIEVhc3R3YXJkcy4gV2UmcnNxdW87ZCBsaWtlIHRvIHNhaWwgZnJvbSBvbmUgaXNsYW5kIHRvIGFub3RoZXIuIEZvciBob3cgbWFueSBwYWlycyBvZiBpc2xhbmRzIGlzIHRoaXMgcG9zc2libGU/IChOb3RlOiBhIHBhaXIgY29uc2lzdHMgb2YgdHdvIGRpXHVmYjAwZXJlbnQgaXNsYW5kcy4pPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIGEgc2luZ2xlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCB0ZXN0IGNhc2UgaGFzIHRoZSBmb2xsb3dpbmcgZm9ybWF0OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggb25lIG51bWJlciBuIHdpdGggMSAmbGU7IG4gJmxlOyA3NTAwMDogdGhlIG51bWJlciBvZiBpc2xhbmRzLjxcL2xpPlxyXG5cdDxsaT5uIGxpbmVzIHdpdGggdHdvIG51bWJlcnMgeDxzdWI+aTxcL3N1Yj4gYW5kIHk8c3ViPmk8XC9zdWI+IHdpdGggJm1pbnVzOzEwPHN1cD45PFwvc3VwPiAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPjogdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBpc2xhbmRzLiBObyB0d28gaXNsYW5kcyBhcmUgbG9jYXRlZCBhdCB0aGUgc2FtZSBjb29yZGluYXRlcy48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgaW4gdGhlIGlucHV0IFx1ZmIwMWxlLCB0aGUgb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIG51bWJlciwgb24gYSBzaW5nbGUgbGluZTogdGhlIG51bWJlciBvZiBwYWlycyBvZiBpc2xhbmRzIGZvciB3aGljaCB5b3UgY2FuIHNhaWwgZnJvbSBvbmUgdG8gdGhlIG90aGVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==