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.

Game turn	Alice's picked range	Bob's picked number	The range set after
Before the game start			$$$ \{ [1, 5] \} $$$
1	$$$[1, 5]$$$	$$$3$$$	$$$ \{ [1, 2], [4, 5] \}$$$
2	$$$[1, 2]$$$	$$$1$$$	$$$ \{ [2, 2], [4, 5] \} $$$
3	$$$[4, 5]$$$	$$$5$$$	$$$ \{ [2, 2], [4, 4] \} $$$
4	$$$[2, 2]$$$	$$$2$$$	$$$ \{ [4, 4] \} $$$
5	$$$[4, 4]$$$	$$$4$$$	$$$ \{ \} $$$ (empty set)

Game on Ranges

Examples