You are scheduling a tournament. There are n teams. There are competitions against every pair of teams. You can schedule a competition each day. For each team, it will arrive in the day when its first competition holds, and leave after its last competition finishes.
For example, there are 3 teams and the schedule is (1,2), (1,3), (2,3). The first team will arrive in day 1, and leave in day 2. It will stay for two days. The second team will stay for three days. The third team will stay for two days.
You want to find a schedule minimizing the sum of days they stay.

The first line contains one integer  — the number of test cases.
For each test cases, the first line contains one integer .

For each test cases, output n(n-1)/2  lines. Each line contains two integers  - the competition you schedule in this day.

2
3
4

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