一位面包师有 $N$ 个来自顾客的订单需要完成，但他每天只能处理一个订单。对于第 $i$ 个订单，面包师需要花费 $D_i$ ($1 \le D_i \le 1000$) 个连续的天数来完成；然而，每延迟一天，面包师必须支付 $S_i$ ($1 \le S_i \le 10000$) 的罚款。例如，如果面包师收到四个制作饼干的订单，每个订单所需天数分别为 3, 1, 2, 5，且每天延迟的罚款分别为 4, 1000, 2, 5。如果面包师的工作顺序是 1 2 3 4，罚款将是 $4 \times 0 + 1000 \times 3 + 2 \times 4 + 5 \times 6 = 3038$；但如果工作顺序是 2 1 3 4，罚款将是 $1000 \times 0 + 4 \times 1 + 2 \times 4 + 5 \times 6 = 42$，因此后者的罚款较少。请编写一个程序，帮助面包师找出罚款最少的工作顺序。

输入格式

输入的第一行包含一个正整数 $T$，表示数据组数。接下来有 $T$ 组数据。对于每组数据，第一行包含一个 $1$ 到 $1000$ 之间的整数 $N$，表示订单数量，随后有 $N$ 行，每行包含两个由空格分隔的整数，依次表示每个订单所需的天数 $D_i$ 和每天延迟的罚款 $S_i$。

输出格式

对于每组数据，在一行中输出罚款最少的工作顺序。每个工作用其编号表示，并用空格分隔。如果存在多组答案，请输出字典序最小的那一组。注意，每组工作从 1 开始编号。

数据范围

• $1 \le T \le 1000$
• $1 \le N \le 1000$
• $1 \le D_i \le 1000, \forall 1 \le i \le N$
• $1 \le S_i \le 10000, \forall 1 \le i \le N$

样例

输入 1

2
4
3 4
1 1000
2 2
5 5
5
3 4
1 1000
8 8
2 2
5 6

输出 1

2 1 3 4
2 1 5 3 4