human
PYTHON3 solution for "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 ≤ d ≤ r). Then Alice removes [l, r] from S and puts into the set S the range [l, d - 1] (if l ≤ d - 1) and the range [d + 1, r] (if d + 1 ≤ 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 ≤ t ≤ 1000). Description of the test cases follows.

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

Each of the next n lines contains two integers l and r (1 ≤ l ≤ r ≤ 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. 

Example

Input

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...":


 ... Can you provide a Python code to find out his numbers d from Alice's ranges, and so he asks you for help with your programming skill?
assistant
#Here is Python code to find out his numbers d from Alice's ranges, and so he asks you for help with your programming skill.
 
def main():
    
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        items = [] # store (l, -r)
        for _ in range(n):
            l, r = readIntArr()
            items.append((l, -r))
        items.sort()
        for i, (l, r) in enumerate(items):
            r *= -1
            if l == r:
                allans.append((l, l, l))
            else:
                l2, r2 = items[i + 1]
                r2 *= -1
                if l == l2:
                    d = r2 + 1
                else:
                    d = l
                allans.append((l, r, d))
        allans.append(['\n'])
    multiLineArrayOfArraysPrint(allans)
    
    return

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ansArr):
    print('! {}'.format(' '.join([str(x) for x in ansArr])))
    sys.stdout.flush()
 
inf=float('inf')
# MOD=10**9+7
# MOD=998244353

from math import gcd,floor,ceil
import math
# from math import floor,ceil # for Python2
 
for _abc in range(1):
    main()