在阿德尼亚（Ardenia）当一名农民是一项艰巨的工作。这不仅是指他们必须放牧绵羊的干燥而恶劣的环境。政府（实际上是国王本人）希望他的子民去侵略外国领土，而不是收获自己的土地，因此竭力让贫苦农民的生活变得尽可能艰难。所有的困难都始于一个看似简单的任务：购买一片土地，称为农场地块（farming parcel）。

整个农耕领土是一个由正方形方格组成的巨大矩形网格；一个农场地块由其中的一些方格组成。起初，农民购买了一组初始方格；他的地块最初仅由这些方格组成。然而，实际的农场地块是通过借助绳子和立柱，通过重复以下步骤来确定的：

• 在当前农场地块的每个方格中心插一根立柱。
• 用一根绳子围住所有立柱，形成包围所有立柱的最小区域。
• 新的农场地块是与该区域有非空交集的所有方格的集合。仅与该区域共享一条边或一个顶点的方格不计入内。

当然，通过执行上述操作，地块只可能扩大，因此每个农民都会确保重复这些步骤，直到农场地块不再发生变化；我们称这样的地块为最终地块（final）。下图展示了一个例子。初始农场地块由四个方格组成（图 A），经过一次迭代后它有所扩大（图 B），再经过一次迭代后达到最终状态（图 C）。

然而，事实表明，即使农民没有购买所有的初始方格，而只是购买了它们的一个子集，最终的农场地块有时也会是相同的。具有这种性质的子集被称为有效的（valid）。农民想知道，他有多少种方式可以选择一个有效的初始方格子集。

输入格式

输入包含多个测试用例。输入的第一行包含一个正整数 $Z \le 50$，表示测试用例的数量。接下来是 $Z$ 个测试用例。

每个测试用例的第一行包含一个正整数 $n \le 10^6$，表示地块的初始方格数量。接下来的 $n$ 行，每行包含两个整数 $x_i, y_i \in [-10^9, 10^9]$，表示这些方格的坐标。所有初始方格的坐标互不相同。

输出格式

对于每个测试用例，设 $k$ 为初始方格的有效子集数量。你应该输出一行，包含 $k \bmod (10^9 + 7)$ 的值。

样例

输入样例 1

2
4
0 0
0 1
0 2
0 3
5
0 0
-1 0
1 0
0 -1
0 1

输出样例 1

4
2