github.com/captn3m0/codechef.git

---
languages_supported:
    - NA
title: H3
category: NA
old_version: true
problem_code: H3
tags:
    - NA
layout: problem
---
###  All submissions for this problem are available. 

After learning about congruent triangles in his recent mathematics lesson, Johnny has become very excited. He has even invented an interesting counting problem involving congruent triangles!

Recall that two triangles are congruent if their corresponding sides are equal in length and their corresponding angles are equal in size. A lattice triangle is a triangle such that the coordinates of all its vertices are integers. Johnny's problem can now be described as follows:

You are given an integer M and a lattice triangle ABC all of whose vertices (A, B, and C) are inside rectangle RM. RM is the rectangle having (0,0) as its bottom-left corner and (M,M) as its top-right corner. In other words, 0 ≤ xA, yA, xB, yB, xC, yC ≤ M. The problem is to count the number of lattice triangles congruent to ABC also having all their vertices inside the rectangle RM.

Could you help Johnny write a program to solve this problem?

### Input

The first line contains t, the number of test cases (about 10). Then t test cases follow. Each test case has the following form:

- The first line contains two numbers M and K (1≤ M ≤ 1000, 1≤ K ≤1000). K is the number of given triangles.
- Each line in the next K lines contains 6 integers xA, yA, xB, yB, xC, yC (0 ≤ xA, yA, xB, yB, xC, yC≤ M) describing a triangle ABC. It is guaranteed that ABC is always a triangle (i.e., non-degenerate).

The input for successive test cases is separated by a blank line.

### Output

For each test case, output a line containing the string "Case #T:" where T should be replaced by the corresponding test case number.

Then, K lines should follow, each line containing the number of triangles having vertices inside the rectangle RM, congruent to the corresponding triangle given in the input.

Print a blank line after each test case.

### Example

<pre><b>Input:</b>
2

2 2
0 0 0 2 2 0
0 0 1 1 2 0

3 2
0 0 0 2 2 0
0 0 1 1 2 0

<b>Output:</b>
Case #1:
4
8

Case #2:
16
24
</pre>### Output details

The 8 triangles congruent to the second triangle (in the first test case) are presented in the following figure:

![](/themes/abessive/images/contests/h3.png)