Regetni

Hello, Earthling. We come from the planet Regetni, and we need your help to make a great deal of money — perhaps we will even share some of it with you.

The trouble is that in our world everything must be an integer. It is even enforced by law: no other kind of number is allowed for anything. So it should not surprise you that we plan our cities using integer coordinate systems. Until now only axis-aligned rectangular plots of land have been sold, but our professor Elgnairt recently had the revolutionary idea to sell triangular plots too. We believe high society will love the concept and that it will make us rich.

Unfortunately the professor patented his idea, so we cannot simply use it. We need his permission, and being a true scientist he will not grant it until we solve one of his riddles. That is where you come in, because we hear you are a genius.

The professor's riddle goes like this: given some candidate corner points, determine how many triangles of integer area can be built from them. Degenerate triangles with empty area (that is, straight lines) must be counted too, since 0 is an integer. To be precise, count the number of triangles whose three corners are three distinct points from the given set of points. All points in a scenario are distinct — there are no duplicates. Here are some examples:

Example a) shows a triangle with integer area (namely 3); b) shows one with non-integer area; c) shows a degenerate triangle with empty area (that is, zero, so count it!); d) shows four points, any three of which build a triangle of integer area; and e) shows four points from which no integer-area triangle can be built at all.

Hint: the area $A$ of a triangle with corners $(x_1, y_1)$, $(x_2, y_2)$ and $(x_3, y_3)$ can be computed as

$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}$

Try to make clever use of this formula.

The first line contains the number of scenarios. Each scenario is given on one line: first the number $N$ of distinct points in that scenario ($0 \le N \le 10000$), followed by $N$ pairs of integers, each pair describing one point $(x_i, y_i)$ with $-100000 \le x_i, y_i \le 100000$. All of these numbers are separated by single spaces.

For each scenario, first print a line "Scenario #i:", where $i$ is the scenario number starting at 1. Then print a single line containing the number of triangles of integer area whose three distinct corners are among the given points. Print a blank line after each scenario.