对于一组配对 $S=\{(a_1,b_1),(a_2,b_2),\dots,(a_m,b_m)\}$，其中对所有 $1\le i\le m$ 均有 $a_i<b_i$，我们定义 $f(S)$ 和 $g(S)$ 如下：

• 将每个 $(a_i,b_i)$ 视为数轴上的线段，$f(S)$ 为这些线段的并集长度。形式化地，$f(S)$ 是满足存在某个 $i$ ($1\le i\le m$) 使得 $[x,x+1]\subseteq[a_i,b_i]$ 的整数 $x$ 的个数。
• 将每个 $(a_i,b_i)$ 视为图中的无向边，$g(S)$ 是至少出现在一个简单环（包含至少 $3$ 条边）上的节点数目。形式化地，$g(S)$ 是满足存在一条路径 $x_1\to x_2\to\dots\to x_k\to x_1$ 的节点 $x_1$ 的个数，其中 $k\ge 3$ 且所有 $x_1,x_2,\dots,x_k$ 互不相同。

例如，对于 $S=\{(1,2),(2,4),(1,4),(4,5),(6,7)\}$，可得到 $f(S)=5$，$g(S)=3$。

给定 $n$ 个互不相同的配对。你需要从中选出一个子集 $S'$，使得 $f(S')-g(S')$ 最大化。你需要输出所选配对的编号。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数 $t$ ($1\le t\le 10^4$)。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1\le n\le 3\cdot 10^3$)。

接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1\le a_i<b_i\le 2n$)，表示一个配对。

保证同一测试用例内的所有配对互不相同。

保证所有测试用例的 $n^2$ 之和不超过 $9\cdot 10^6$。

输出格式

对于每个测试用例，第一行输出一个整数 $k$ ($0\le k\le n$) — 所选子集 $S'$ 的大小。

接下来一行输出 $k$ 个整数 $i_1,i_2,\dots,i_k$ ($1\le i_1,i_2,\dots,i_k\le n$) — 所选配对的编号。注意编号必须互不相同。

样例

输入：

2
1
1 2
4
1 2
2 3
1 3
3 5

输出：

1
1
3
1 2 4

说明

在第一个测试用例中，如果不选任何配对（即 $S'=\varnothing$），则 $f(S')-g(S')=0-0=0$；若选取第一个配对，则 $f(S')-g(S')=1-0=1$。因此最优方案是选取第一个配对。