1425 - A simple problem

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.