Problem Statement

You are given a positive integer $N$ and sequences of positive integers of length $N$: $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$. It is guaranteed that $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ are all distinct.

A movie theater has $N$ seats arranged in a row from left to right. The $i$-th seat from the left is called seat $i$.

$N$ people, numbered $1$ to $N$, visit this movie theater. You assign one seat to each person. Let $P_i$ be the seat assigned to person $i$. Then, person $i$ arrives at time $L_i$, crosses seats $1,2,\ldots,P_i-1$ to sit in seat $P_i$, and leaves at time $R_i$, crossing seats $1,2,\ldots,P_i-1$ to exit.

The dissatisfaction of person $i$ is the number of times other people cross seat $P_i$ during the time interval from time $L_i$ to time $R_i$ (not including exactly $L_i$ and $R_i$).

Find the lexicographically smallest permutation $P$ of $(1,2,\ldots,N)$ that minimizes the total dissatisfaction of all people from $1$ to $N$.

You are given $T$ test cases, so find the answer for each.

Constraints

• $1\le T\le 500$
• $1\le N\le 500$
• $1\le L_i < R_i\le 2\times N$
• $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ are all distinct.
• The sum of $N$ over all test cases is at most $500$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Output $T$ lines.

The $i$-th line should contain the lexicographically smallest permutation $P$ of $(1,2,\ldots,N)$ that minimizes the total dissatisfaction of all people from $1$ to $N$ for the $i$-th test case, separated by spaces.