A rectangle with sides $A$ and $B$ is cut into rectangles with cuts parallel to its sides. For example, if $p$ horizontal and $q$ vertical cuts were made, $(p + 1) \cdot (q + 1)$ rectangles were left after the cutting. After the cutting, rectangles were of $n$ different types. Two rectangles are different if at least one side of one rectangle isn't equal to the corresponding side of the other. Note that the rectangle can't be rotated, this means that rectangles $a \times b$ and $b \times a$ are considered different if $a \neq b$.
For each type of rectangles, lengths of the sides of rectangles are given along with the amount of the rectangles of this type that were left after cutting the initial rectangle.
Calculate the amount of pairs $(A; B)$ such as the given rectangles could be created by cutting the rectangle with sides of lengths $A$ and $B$. Note that pairs $(A; B)$ and $(B; A)$ are considered different when $A \neq B$.
## Input
The first line consists of a single integer $n$ ($1 \leq n \leq 2 \cdot 10^{5}$) — amount of different types of rectangles left after cutting the initial rectangle.
The next $n$ lines each consist of three integers $w_{i}, h_{i}, c_{i}$ $(1 \leq w_{i}, h_{i}, c_{i} \leq 10^{12})$ — the lengths of the sides of the rectangles of this type and the amount of the rectangles of this type.
It is guaranteed that the rectangles of the different types are different.
## Output
Output one integer — the answer to the problem.
[samples]
## Note
In the first sample there are three suitable pairs: $(1; 9)$, $(3; 3)$ and $(9; 1)$.
In the second sample case there are 6 suitable pairs: $(2; 220)$, $(4; 110)$, $(8; 55)$, $(10; 44)$, $(20; 22)$ and $(40; 11)$.
Here the sample of cut for $(20; 22)$.
<center></center>The third sample has no suitable pairs.
一个边长为 $A$ 和 $B$ 的矩形被沿平行于其边的方向切割成若干小矩形。例如，若进行了 $p$ 条水平切和 $q$ 条垂直切，则切割后剩下 $(p + 1) \dot.op (q + 1)$ 个矩形。切割后，得到了 $n$ 种不同类型的矩形。两个矩形不同，当且仅当至少有一个矩形的某一边长不等于另一个矩形对应的边长。注意，矩形不能旋转，这意味着边长为 $a \times b$ 和 $b \times a$ 的矩形若 $a \ne b$ 则被视为不同。
对于每种类型的矩形，给出了其边长以及切割后剩余的该类型矩形的数量。
计算满足条件的 $(A \; B)$ 对的数量，使得可以通过切割边长为 $A$ 和 $B$ 的矩形得到给定的所有矩形。注意，当 $A \ne B$ 时，$(A \; B)$ 和 $(B \; A)$ 被视为不同的对。
第一行包含一个整数 $n$ ($1 \lt.eq n \lt.eq 2 \dot.op 10^5$) —— 切割后剩余的不同类型矩形的数量。
接下来的 $n$ 行，每行包含三个整数 $w_i, h_i, c_i$ ($1 \lt.eq w_i, h_i, c_i \lt.eq 10^{12}$) —— 表示该类型矩形的边长及该类型矩形的数量。
保证不同类型的矩形互不相同。
输出一个整数 —— 问题的答案。
在第一个样例中，有三个满足条件的对：$(1 \; 9)$、$(3 \; 3)$ 和 $(9 \; 1)$。
在第二个样例中，有六个满足条件的对：$(2 \; 220)$、$(4 \; 110)$、$(8 \; 55)$、$(10 \; 44)$、$(20 \; 22)$ 和 $(40 \; 11)$。
下图是 $(20 \; 22)$ 的切割示例。
第三个样例没有满足条件的对。
## Input
第一行包含一个整数 $n$ ($1 \lt.eq n \lt.eq 2 \dot.op 10^5$) —— 切割后剩余的不同类型矩形的数量。接下来的 $n$ 行，每行包含三个整数 $w_i, h_i, c_i$ ($1 \lt.eq w_i, h_i, c_i \lt.eq 10^{12}$) —— 表示该类型矩形的边长及该类型矩形的数量。保证不同类型的矩形互不相同。
## Output
输出一个整数 —— 问题的答案。
[samples]
## Note
在第一个样例中，有三个满足条件的对：$(1 \; 9)$、$(3 \; 3)$ 和 $(9 \; 1)$。在第二个样例中，有六个满足条件的对：$(2 \; 220)$、$(4 \; 110)$、$(8 \; 55)$、$(10 \; 44)$、$(20 \; 22)$ 和 $(40 \; 11)$。下图是 $(20 \; 22)$ 的切割示例。第三个样例没有满足条件的对。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of distinct rectangle types.
For each $ i \in \{1, \dots, n\} $, let $ (w_i, h_i, c_i) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \times \mathbb{Z}^+ $ denote the width, height, and count of rectangles of type $ i $.
Let $ \mathcal{R} = \{ (w_i, h_i, c_i) \mid i = 1, \dots, n \} $ be the multiset of rectangle types.
Let $ A, B \in \mathbb{Z}^+ $ be the dimensions of the original rectangle.
**Constraints**
1. All $ w_i, h_i, c_i \geq 1 $, and $ c_i \leq 10^{12} $, $ n \leq 2 \cdot 10^5 $.
2. All rectangle types are distinct: $ (w_i, h_i) \neq (w_j, h_j) $ for $ i \neq j $.
3. The original rectangle is partitioned into a grid of smaller rectangles via axis-aligned cuts:
- There exist integers $ p, q \geq 0 $ such that the grid has $ (p+1) $ rows and $ (q+1) $ columns.
- Each small rectangle has width from the set $ W = \{ w_i \} $ and height from the set $ H = \{ h_i \} $.
- All rectangles in the same row have equal height; all in the same column have equal width.
- Thus, the grid is defined by a multiset of column widths $ \{x_1, \dots, x_{q+1}\} $ and row heights $ \{y_1, \dots, y_{p+1}\} $, such that:
$$
A = \sum_{j=1}^{q+1} x_j, \quad B = \sum_{i=1}^{p+1} y_i
$$
- Each cell $ (i,j) $ contains a rectangle of size $ x_j \times y_i $, and the total count of rectangle type $ (w, h) $ is the number of pairs $ (i,j) $ such that $ x_j = w $ and $ y_i = h $.
- Therefore, for each type $ (w_i, h_i) $, we must have:
$$
c_i = \text{count of } j \text{ with } x_j = w_i \quad \times \quad \text{count of } i \text{ with } y_i = h_i
$$
**Objective**
Count the number of ordered pairs $ (A, B) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ such that there exist multisets of positive integers $ X = \{x_1, \dots, x_m\} $, $ Y = \{y_1, \dots, y_k\} $ satisfying:
- $ A = \sum X $, $ B = \sum Y $,
- For each $ i \in \{1, \dots, n\} $, $ c_i = f_X(w_i) \cdot f_Y(h_i) $,
where $ f_X(w) = |\{ j \mid x_j = w \}| $, and similarly for $ f_Y $.
- The set of distinct rectangle types produced is exactly $ \{ (w_i, h_i) \mid i=1,\dots,n \} $, and no other types exist.
Output the number of such ordered pairs $ (A, B) $.