기다림 적은 출근길 Output Only 제출 불가 컴파일 명령

나나는 기다림이 많아 지루한 출근 시간을 면하기 위해, 기다림이 적은 출근을 해 보기로 했습니다.

나나는 지하철 0호선을 타고 출근합니다. 0호선에는 총 N + 1개의 역이 있으며, 각 역에는 0 이상 N 이하의 정수 번호가 시발역에서부터 종착역까지 차례대로 붙어 있습니다. 나나의 집은 0번 역에, 회사는 N번 역에 있습니다. 이 노선은 매우 광활한 영토를 가로지르기 때문에, 열차들은 서로 인접한 두 역 사이만 지나다닙니다.

각 열차에는 번호가 붙어있는데, 이 중 i (1 ≤ i ≤ N)번 열차는 (i - 1)번 역에서 출발하여 i번 역에 도착합니다. (안타깝게도, 이 열차를 타고 i번 역에서 (i - 1)번 역으로 갈 수는 없습니다.) 이 열차는 B_i분을 기준으로 그 이전에나 그 이후에나 C_i분 간격으로 (i - 1)번 역에서 출발합니다. 예를 들어서 B_i = 5, C_i = 3이라면 ... -4, -1, 2, 5, 8, 11, 14 ... 분에 출발한다는 것입니다. 두 역 사이를 이동하는 데에는 D_i분이 걸립니다. 즉, 출발한 지 D_i분이 지났을 때 i번 역에 도착합니다.

어떤 역에서 열차 X가 도착하는 시각을 t₁, 열차 Y가 출발하는 시각을 t₂로 둘 때, t₁ ≤ t₂를 만족한다면, 나나는 열차 X에서 내려 t₂ - t₁분을 기다린 후 열차 Y로 갈아탈 수 있습니다. 나나는 번호가 1 이상 N 이하인 열차들만을 이용하여, {(N번 열차에서 내린 시각) - (1번 열차를 탄 시각)}의 값을 최소화하여 출근하고 싶습니다. 이 값은 대체 얼마일까요??

입력 형식

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1,000)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 지하철 노선 수 N이 주어집니다. 그 다음 N개의 줄이 주어지는데, 이 중 i (1 ≤ i ≤ N)번째 줄에는 세 개의 자연수 B_i, C_i, D_i가 공백을 사이로 두고 주어집니다.

출력 형식

각 테스트 케이스마다, 답을 분 단위로 한 줄에 하나씩 출력합니다.

입력 파일 정보

답안 생성 및 제출 방법

여기에서 입력 파일을 내려받아서, 위 표에 따라 출력 파일을 만듭니다. 제출하는 방법은 두 가지가 있습니다.

• 모든 출력 파일을 하나의 zip 파일에 압축하여 제출합니다. 다른 폴더 안에 출력 파일을 넣고 압축하는 등의 행위를 할 시 업로드 공격으로 의심되어 업로드가 즉시 차단됩니다.
• 각 출력 파일을 하나씩 업로드하여 제출합니다.

예제