张教授在平面上画了 $n$ 个点，并方便地将它们标记为 $1, 2, \dots, n$。第 $i$ 个点的坐标为 $(x_i, y_i)$。张教授想知道“最佳集合”（best sets）的数量。由于数值可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

一个集合 $P$（$P$ 包含点的标签）被称为“最佳集合”，当且仅当 $P$ 中至少存在一对“最佳点对”（best pair）。两个数字 $u$ 和 $v$（$u, v \in P, u \neq v$）被称为“最佳点对”，如果对于每一个 $w \in P$，都有 $f(u, v) \geq g(u, v, w)$，其中 $f(u, v) = \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2}$ 且 $g(u, v, w) = \frac{f(u, v) + f(v, w) + f(w, u)}{2}$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \leq n \leq 1000$)：点的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$)：第 $i$ 个点的坐标。

测试数据不超过 250 组，且所有测试数据中 $n$ 的总和不超过 40 000。

输出格式

对于每组测试数据，输出一个整数：最佳集合的数量对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

3
3
1 1
1 1
1 1
3
0 0
0 1
1 0
1
0 0

样例输出 1

4
3
0