1425 - A simple problem

Time Limit: 1s Memory Limit: 128MB

Submissions: 111 Solved: 31
Description

 

xiaoY is crazy about determinant, One day he ask Mr HH a question “Mr HH, I have a hard computing problem on determinant, there is N point on 3-D plane (all point is grid, which means coordinates are integer), and we define

Now the question is how many Det(pi,pj,pk) is Multiple of 3.” (i != j, j != k, k != i)

Input

The first line is an integer T, means T cases followed:

Each case is described in the following way:

An integer N (N<=10000)

N lines followed, each line is an point xi yi zi(|xi|<2*10^9,|yi|<2*10^9,|zi|<2*10^9 )

Output

For each case output the number of Det which is Multiple of 3.

Sample Input
2
3
1 1 1
1 1 2
1 1 3
3
1 1 2
3 3 2
5 6 8
Sample Output
Case #1: 6
Case #2: 0
Hint

 

Because answer may be too large, long long is recommended

Source