Regetni

지구인이여, 안녕하세요. 우리는 Regetni 행성에서 왔고, 큰돈을 벌기 위해 당신의 도움이 필요합니다. 어쩌면 그중 일부를 당신에게 나누어 줄지도 모릅니다.

문제는 이렇습니다. 우리 세계에서는 모든 것이 정수여야 합니다. 그것도 법으로 강제되어 있어서, 그 무엇에도 정수가 아닌 수는 허용되지 않습니다. 그러니 우리가 도시를 계획할 때 정수 좌표계를 쓰는 것도 놀랄 일이 아닙니다. 지금까지는 축에 평행한 직사각형 토지만 팔렸지만, 최근 Elgnairt 교수가 삼각형 모양의 토지도 팔자는 혁명적인 아이디어를 냈습니다. 상류층이 이 개념을 아주 좋아할 것이고, 그러면 우리는 부자가 될 것이라 믿습니다.

안타깝게도 교수가 이 아이디어를 특허로 등록해 버려서 우리 마음대로 쓸 수가 없습니다. 교수의 허락이 필요한데, 진정한 과학자인 그는 자신이 낸 수수께끼를 우리가 풀기 전에는 허락해 주지 않습니다. 바로 여기서 당신이 필요합니다. 당신이 천재라고 들었거든요.

교수의 수수께끼는 이렇습니다. 삼각형의 꼭짓점이 될 수 있는 점들이 주어질 때, 이 점들로 만들 수 있는 넓이가 정수인 삼각형이 몇 개인지 구하세요. 넓이가 0인, 즉 하나의 직선으로 찌그러진(퇴화한) 삼각형도 세어야 합니다. 0도 정수이기 때문입니다. 더 정확히 말하면, 주어진 점 집합에서 서로 다른 세 점을 꼭짓점으로 하는 삼각형 중 넓이가 정수인 것의 개수를 세면 됩니다. 한 시나리오 안의 모든 점은 서로 다릅니다. 즉, 중복되는 점은 없습니다. 몇 가지 예시는 다음과 같습니다.

예시 a)는 넓이가 정수(즉 3)인 삼각형을, b)는 넓이가 정수가 아닌 삼각형을, c)는 넓이가 0인 퇴화한 삼각형(0이므로 세어야 합니다!)을 보여 줍니다. d)는 어느 세 점을 골라도 넓이가 정수인 삼각형이 되는 네 점을, e)는 어떤 세 점으로도 넓이가 정수인 삼각형을 만들 수 없는 네 점을 보여 줍니다.

힌트: 꼭짓점이 $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$인 삼각형의 넓이 $A$는 다음과 같이 계산할 수 있습니다.

$A = \frac{|x_1 y_2 - y_1 x_2 + x_2 y_3 - y_2 x_3 + x_3 y_1 - y_3 x_1|}{2}$

이 공식을 잘 활용해 보세요.

첫째 줄에는 시나리오의 수가 주어집니다. 각 시나리오는 한 줄로 주어집니다. 먼저 그 시나리오에 있는 서로 다른 점의 개수 $N$ ($0 \le N \le 10000$)이 주어지고, 이어서 $N$개의 정수 쌍이 주어집니다. 각 쌍은 하나의 점 $(x_i, y_i)$를 나타내며 $-100000 \le x_i, y_i \le 100000$입니다. 이 모든 수는 하나의 공백으로 구분됩니다.

각 시나리오마다 먼저 "Scenario #i:" 형식의 줄을 출력합니다. 여기서 $i$는 1부터 시작하는 시나리오 번호입니다. 그다음 줄에는 주어진 점들 중 서로 다른 세 점을 꼭짓점으로 하는 넓이가 정수인 삼각형의 개수를 출력합니다. 각 시나리오의 출력 뒤에는 빈 줄을 하나 출력합니다.