Migrated from Lutece 3056 一闪一闪亮晶晶

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

天空中有 $n$ 颗星星在闪烁着诡异的光。在每个时刻，第 $i$ 颗星星有 $u_i/v_i(1 \leq u_i < v_i<P=31607)$ 的概率闪光。请计算出某个瞬间闪光的星星组成凸包面积的期望值。

已知素数 $P = 31607$，可以证明答案可以表示为一个不可约分数 $p/q$，其中 $p$ 和 $q$ 是整数并且 $q \not \equiv 0 \pmod{P}$。

Input

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示数据的组数。

对于每组数据，第一行包含一个整数 $n(1 \le n \le 1000)$，表示星星的颗数。

接下来 $n$ 行中，每行包含四个整数 $x_i, y_i, u_i, v_i(-1000 \le x_i,y_i \le 1000, 1 \leq u_i < v_i<P=31607)$ 表示第 $i$ 颗星星的坐标和闪光的概率，保证没有任何两个星星坐标相同。

保证最多有三组数据 $n>20$。

Output

对于每组数据单独输出一行，包含一个整数 $p \cdot q^{-1} \bmod P$ 表示答案。

Samples

2
4
0 0 1 2
1 0 1 2
0 1 1 2
1 1 1 2
4
0 0 1 2
1 0 1 2
-1 0 1 2
0 1 1 2

21730
21730

Resources

2023 UESTC ICPC Training for Geometry