Problem Statement

SPD-kun received a multiset $S$ consisting of $N$ matrices as a reward for running an event.

The shape of the $i$-th ($1 \le i \le N$) matrix is $H_i \times W_i$.

Since many matrices take up a lot of space, SPD-kun intends to multiply all the matrices together into $1$ matrix.

Specifically, he repeats the operation below until $S$ has $1$ element, or there are no longer $2$ elements that can be multiplied.

• Choose $2$ elements $X$ , $Y$ from $S$ such that $X \cdot Y$ can be computed. Remove $X$ , $Y$ from $S$ and add $X \cdot Y$ to $S$.

Find the number of different possible shapes of the matrix when $S$ finally has $1$ element. However, if $S$ cannot be reduced to $1$ element no matter how the operations are performed, output $0$.

Note that for $2$ matrices $X$ (of shape $H_X \times W_X$) and $Y$ (of shape $H_Y \times W_Y$), $ X \cdot Y $ can be computed if and only if $ W_X = H_Y $, and its shape is then $H_X \times W_Y$.

Also, the shapes of $2$ matrices are said to be different if at least one of the number of rows and the number of columns differs.

Input

$N$
$H_1\ W_1$
$H_2\ W_2$
$\vdots$
$H_N\ W_N$

• All inputs are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le H_i \le 2 \times 10^5$
• $1 \le W_i \le 2 \times 10^5$

Output

Print a newline at the end.

Sample

3
1 2
2 2
2 3

1

2
7 8
8 7

2

5
4 2
6 3
5 9
7 1
8 10

0