有 $N$ 对已经分开的夫妻聚集在一起寻找新的伴侣。 每对夫妻由一名男性和一名女性组成，总共有 $N$ 名互不相同的男性和 $N$ 名互不相同的女性。

他们坐在编号为 $1$ 到 $2N$ 的 $2N$ 把椅子上，满足以下条件：

• 任意两个人不会坐在同一把椅子上；每把椅子上恰好坐着一人。
• 对于第 $i$ 对已分开的夫妻，男性坐在椅子 $L_i$，女性坐在椅子 $R_i$（$1 \le i \le N$）。
• $1 \le L_i < R_i \le 2N$。
• 不存在一对 $(i, j)$（$1 \le i, j \le N$）使得 $L_i < L_j < R_i < R_j$。

他们想要组成 $N$ 对新的情侣，满足以下条件：

• 每对新情侣由一名男性和一名女性组成，并且每个人恰好属于一对新情侣。
• 任何人都不能与其原来的伴侣配对。
• 对于任意一对新情侣，若男性坐在椅子 $l$，女性坐在椅子 $r$，则必须满足 $l < r$。

例如，考虑 $N = 3$ 且 $(L_1, R_1) = (1, 6)$，$(L_2, R_2) = (2, 3)$，$(L_3, R_3) = (4, 5)$。

• 坐在椅子 $1$ 的男性和坐在椅子 $6$ 的女性不能组成新情侣，因为他们是原来的夫妻。
• 坐在椅子 $4$ 的男性和坐在椅子 $3$ 的女性不是原来的夫妻，但他们也不能组成新情侣，因为男性的椅子编号更大。

另一方面：

• 坐在椅子 $1$ 的男性和坐在椅子 $3$ 的女性可以组成新情侣。
• 坐在椅子 $2$ 的男性和坐在椅子 $5$ 的女性可以组成新情侣。
• 坐在椅子 $4$ 的男性和坐在椅子 $6$ 的女性可以组成新情侣。

这样就可以组成满足所有条件的 $3$ 对情侣。

你的任务是计算组成 $N$ 对新情侣的不同方案数。 如果存在至少一对新情侣只出现在两种方案中的某一种里，则认为这两种方案不同。

在上述例子中，可以证明恰好只有一种组成 $3$ 对情侣的方案，因此答案为 $1$。

由于方案数可能非常大，请输出对 $10^9 + 7$ 取模后的结果。

你需要在一次输入中解决 $T$ 组测试数据。

限制

• 所有给定值均为整数。
• $1 \le T \le 100$
• $1 \le N \le 3000$
• 令 $S$ 为所有测试数据中 $N$ 的总和；$1 \le S \le 3000$
• $1 \le L_i < R_i \le 2N$（$1 \le i \le N$）
• $L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N$ 两两不同。
• 不存在一对 $(i, j)$（$1 \le i, j \le N$）使得 $L_i < L_j < R_i < R_j$。

子任务

子任务 1（11 分）

• $N \le 8$，$S \le 800$。

子任务 2（32 分）

• $N \le 16$，$S \le 1600$。

子任务 3（20 分）

• $N \le 100$，$S \le 2000$。
• 不存在三元组 $(i, j, k)$（$1 \le i, j, k \le N$）使得 $L_i < L_j < R_i < L_k < R_j < R_k$。

子任务 4（27 分）

• $N \le 100$，$S \le 2000$。

子任务 5（10 分）

• 无额外限制。

输入格式

• 第一行包含一个整数 $T$，表示测试数据组数。
• 接下来给出 $T$ 组测试数据。

• 每组测试数据由 $N+1$ 行组成：

  • 第一行包含整数 $N$。
  • 第 $(1+i)$ 行包含两个整数 $L_i$ 和 $R_i$。

输出格式

• 对于每组测试数据，输出一行答案。

样例数据

样例 1

输入

5
1
1 2
2
1 4
2 3
3
1 6
2 5
3 4
3
1 6
2 3
4 5
4
1 8
5 6
2 7
3 4

输出

0
1
2
1
6