Alice and Bob play the following game. Alice has a set $S$ of disjoint ranges of integers, initially containing only one range $[1, n]$. In one turn, Alice picks a range $[l, r]$ from the set $S$ and asks Bob to pick a number in the range. Bob chooses a number $d$ ($l \le d \le r$). Then Alice removes $[l, r]$ from $S$ and puts into the set $S$ the range $[l, d - 1]$ (if $l \le d - 1$) and the range $[d + 1, r]$ (if $d + 1 \le r$). The game ends when the set $S$ is empty. We can show that the number of turns in each game is exactly $n$.

After playing the game, Alice remembers all the ranges $[l, r]$ she picked from the set $S$, but Bob does not remember any of the numbers that he picked. But Bob is smart, and he knows he can find out his numbers $d$ from Alice's ranges, and so he asks you for help with your programming skill.

Given the list of ranges that Alice has picked ($[l, r]$), for each range, help Bob find the number $d$ that Bob has picked.

We can show that there is always a unique way for Bob to choose his number for a list of valid ranges picked by Alice.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$).

Each of the next $n$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$), denoting the range $[l, r]$ that Alice picked at some point.

Note that the ranges are given in no particular order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$, and the ranges for each test case are from a valid game.

Output

For each test case print $n$ lines. Each line should contain three integers $l$, $r$, and $d$, denoting that for Alice's range $[l, r]$ Bob picked the number $d$.

You can print the lines in any order. We can show that the answer is unique.

It is not required to print a new line after each test case. The new lines in the output of the example are for readability only.

Note

In the first test case, there is only 1 range $[1, 1]$. There was only one range $[1, 1]$ for Alice to pick, and there was only one number $1$ for Bob to pick.

In the second test case, $n = 3$. Initially, the set contains only one range $[1, 3]$.

• Alice picked the range $[1, 3]$. Bob picked the number $1$. Then Alice put the range $[2, 3]$ back to the set, which after this turn is the only range in the set.
• Alice picked the range $[2, 3]$. Bob picked the number $3$. Then Alice put the range $[2, 2]$ back to the set.
• Alice picked the range $[2, 2]$. Bob picked the number $2$. The game ended.

In the fourth test case, the game was played with $n = 5$. Initially, the set contains only one range $[1, 5]$. The game's turn is described in the following table.

Samples

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

1 1 1

1 3 1
2 2 2
2 3 3

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

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