Apology

Python3 got TLE with the intended solution.

Problem Statement

Inside an equilateral triangle, we add several line segments, each parallel to one of its three sides.

The $i$-th segment to be added is described using parameters $p_i, \ a_i, \ b_i$ as follows.

• $p_i$ is $0$, $1$, or $2$, and these correspond to the vertices of the equilateral triangle in counterclockwise order.
• Consider the points that internally divide each of the two sides extending from vertex $p_i$ in the ratio $a_i : b_i$, and call them $A$ and $B$, respectively.
• Then the segment $AB$ is the $i$-th segment to be added.

(See also the samples.)

After all the segments have been added, output the number of equilateral triangles formed by the existing line segments.

Input

$N$
$p_1 \ a_1 \ b_1$
:
$p_N \ a_N \ b_N$

The first line contains the number $N$ of segments to add.

If $N$ is at least 1, the following $N$ lines, starting from the second line, contain the information $p_i, \ a_i, \ b_i$ of the segments to add, separated by spaces.

All input values are integers and satisfy the following constraints.

• $0 \leq N \leq 4000$
• $0 \leq p_i \leq 2$
• $1 \leq a_i, b_i$
• $a_i + b_i \leq 4 \times 10^5$
• $(i \neq j)$ ならば, $(p_i \neq p_j)$ または $(a_i : b_i \neq a_j : b_j)$

Output

Output the number of equilateral triangles in the final figure.

Print a newline at the end.

Sample

Sample 1

Input

3
0 1 1
1 1 1
2 1 1

Output

5

The segments are added as shown below, and the final figure contains 5 equilateral triangles.

→ →

Sample 2

Input

4
2 1 1
1 3 1
2 9 3
0 6 2

Output

11

Note that $a_i$ and $b_i$ are not necessarily coprime.

3
0 12 12
1 21 212
2 12 1212

4

0

1