#1054 아직 우리들의 여름은 끝나지 않았다.

문제

지문 언어

아코	아아, 들리시나요? 대기하고 있는 현장 요원은 응답바랍니다.
이오리	여기는 코드네임S. 현장에 도착했다.
치나츠	여기는 코드네임H, 마찬가지로 도착했습니다.
아코	네, 통신 양호함. 전부 확인했습니다. 그럼 지금부터 다시 이번 작전의 개요를 설명 드리겠습니다.
아코	저희 선도부의 하계 합숙 훈련은 오늘 오후 4시를 기해 종료. 복귀가 예정되어 있습니다.
아코	부장님께 전달 드린 오늘의 일정은, 오후에 있을 전체 사격 훈련뿐.
아코	다만 그 훈련을 실행하기 전, 부장님께선 짬을 내어 해변에서 수영 연습을 하고자 하셨습니다.
아코	그 말인 즉……. 부장님 또한 이 시간을 휴가로 생각해주시기 시작하셨다는 증거!
아코	그렇다면 저희의 임무는 간단합니다. 부장님의 휴가를 마지막까지 전력으로 서포트하는 것!
아코	구체적으로는 혹시라도 있을지 모를 해변의 위험요소를 배제하고, 해변을 통제하는 것으로, 부장님이 휴가를 즐기실 수 있는 무대를 세팅하는 겁니다!
이오리	아무리 생각해도, 이거 폭거 아냐……?
치나츠	그나마 지난번의 소동으로 손님들이 없어서 다행이네요…….
아코	잔말은 됐습니다! 부디! 실수는 절대로 안 돼요!

안녕하세요, 게헨나 학원 선도부의 선임행정관 아코입니다. 오늘 오후 4시까지, 부장님께서 해변에서 안전하게 수영 연습을 하실 수 있도록, 저희는 해변을 완전히 통제합니다. 그리고 저는 그 통제를 위해, 지금부터 요원 투입 순서표를 작성하겠습니다.

$\rule{30em}{0.3pt}$

작전 시간은 $1$ 번부터 $N$ 번까지 총 $N$ 개의 투입 구간으로 나뉩니다. 각 구간에는 현장 요원 $1$ 명만 투입합니다. 또한 현장 요원은 $1$ 번부터 $N$ 번까지 총 $N$ 명이며, 각 요원은 오늘 정확히 한 번씩만 투입됩니다.

첫 번째 줄에 테스트 케이스 수 $T$ 가 주어진다. $(1 \le T \le 100\,000)$

각 테스트 케이스마다 첫 번째 줄에 $N$ 이 주어진다. 다음 $N - 1$ 개 줄에 투입 가능한 시간 구간의 정보가 주어진다. 그중 번째 줄은 , 가 공백으로 구분되어 주어진다. ;

각 테스트 케이스마다 한 줄에 아래 세 정수를 순서대로 공백으로 구분해 출력한다.

예제 1

입력

출력

3 3
3 6
1 0

예제 2

입력

출력

0 0 55