Triangle

Time limit1sMemory limit128 MB

Summary

Count the lattice points strictly inside a lattice triangle given by its three vertices, for many test cases.

Level: Medium7 of 10
Topics: Geometry, Number theory, Math
Solved: No attempts yet

Problem

A lattice point is an ordered pair $(x, y)$ where both $x$ and $y$ are integers. Given the coordinates of the three vertices of a triangle, all of which are lattice points, count how many lattice points lie strictly inside the triangle. Points that lie on an edge or at a vertex do not count.

Input

The input contains several test cases. Each test case consists of six integers $x_1$ , $y_1$ , $x_2$ , $y_2$ , $x_3$ , $y_3$ , the coordinates of the vertices $(x_1, y_1)$ , $(x_2, y_2)$ , and $(x_3, y_3)$ . Every triangle is non-degenerate (it has positive area), and every coordinate satisfies $-15000 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 15000$ . The end of the input is marked by a test case with $x_1 = y_1 = x_2 = y_2 = x_3 = y_3 = 0$ , which must not be processed.

Output

For each test case, print the number of interior lattice points on its own line.

Examples2

Example 1

Input

0 0 1 0 0 1
0 0 5 0 0 5
0 0 0 0 0 0

Expected output

0
6

Example 2
Input
```
0 0 10 0 0 10
0 0 0 0 0 0
```
Expected output
```
36
```