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.

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.

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.