Rational Dimasik

Little Dimasik is a fan of rational numbers. He has $n$ rational numbers $\frac{x_i}{y_i}$. Recently Dimasik learned how to subtract rational numbers.

Every rational number can be written uniquely as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are coprime integers and $b > 0$.

Define the function $d \left( \frac{x_i}{y_i} \right)$ as the denominator of the rational number $\frac{x_i}{y_i}$ in irreducible form. For example, $d(\frac{14}{6}) = d(\frac{7}{3}) = 3$.

Now Dimasik wants to compute $\prod\limits_{1 \le i < j \le n} d \left( \left| \frac{x_i}{y_i} - \frac{x_j}{y_j} \right| \right)\text{.}$ But he soon realized that this problem is too hard for him. Dimasik asks you to help him. The value may be very large, so find it modulo $998\,244\,353$.

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$), the number of rational numbers Dimasik has.

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i \le 10^{9}$, $1 \le y_i \le 10^6$), the numerator and denominator of the $i$-th rational number.

Print a single integer: the answer to the problem modulo $998\,244\,353$.