$N$ pairs of separated couples have gathered in one place to find new partners. Each couple consists of one man and one woman, and altogether there are $N$ distinct men and $N$ distinct women.

They are seated on $2N$ chairs numbered from $1$ to $2N$, satisfying the following conditions:

• No two people sit on the same chair; exactly one person sits on each chair.
• For the $i$-th separated couple, the man sits on chair $L_i$ and the woman sits on chair $R_i$ $(1 \le i \le N)$.
• $1 \le L_i < R_i \le 2N$.
• There is no pair $(i, j)$ $(1 \le i, j \le N)$ such that $L_i < L_j < R_i < R_j$.

They want to form $N$ pairs of new couples satisfying the following conditions:

• Each new couple consists of one man and one woman, and every person belongs to exactly one new couple.
• No one may be paired with their former partner.
• For any new couple, if the man sits on chair $l$ and the woman sits on chair $r$, then $l < r$ must hold.

For example, consider the case $N = 3$ with $(L_1, R_1) = (1, 6)$, $(L_2, R_2) = (2, 3)$, $(L_3, R_3) = (4, 5)$.

• The man on chair $1$ and the woman on chair $6$ cannot form a new couple because they are a former couple.
• The man on chair $4$ and the woman on chair $3$ are not a former couple, but they cannot form a new couple because the man’s chair number is larger.

On the other hand:

• The man on chair $1$ and the woman on chair $3$ can form a new couple.
• The man on chair $2$ and the woman on chair $5$ can form a new couple.
• The man on chair $4$ and the woman on chair $6$ can form a new couple.

In this way, $3$ pairs of couples can be formed satisfying all conditions.

Your task is to compute the number of different ways to form $N$ new couples. Two ways are considered different if there exists at least one new couple that appears in only one of the two ways.

In the example above, it can be shown that there is exactly one way to form $3$ pairs of couples, so the answer is $1$.

Since the number of ways can be very large, output the result modulo $10^9 + 7$.

You must solve $T$ test cases in a single input.

Constraints

• All given values are integers.
• $1 \le T \le 100$
• $1 \le N \le 3000$
• Let $S$ be the sum of $N$ over all test cases; $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$ are all distinct.
• There is no pair $(i, j)$ $(1 \le i, j \le N)$ such that $L_i < L_j < R_i < R_j$.

Scoring

Subtask 1 (11 points)

• $N \le 8$, $S \le 800$.

Subtask 2 (32 points)

• $N \le 16$, $S \le 1600$.

Subtask 3 (20 points)

• $N \le 100$, $S \le 2000$.
• There is no triple $(i, j, k)$ $(1 \le i, j, k \le N)$ such that $L_i < L_j < R_i < L_k < R_j < R_k$.

Subtask 4 (27 points)

• $N \le 100$, $S \le 2000$.

Subtask 5 (10 points)

• No additional constraints.

Input Format

• The first line contains an integer $T$, the number of test cases.
• The following $T$ test cases are given.

• Each test case consists of $N+1$ lines:

  • The first line contains $N$.
  • The $(1+i)$-th line contains two integers $L_i$ and $R_i$.

Output Format

• For each test case, output one line containing the answer.

Example

Example 1

Input

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

Output

0
1
2
1
6