외계인들이 지구를 침략했다. (결국!) 스스로를 방어하지 않으면 죽는다! 아니면 동화되거나. 먹힐 수도 있다. 사실 잘 모르겠다.

외계인들은 다음과 같은 공격 패턴을 따른다. n명의 외계인이 있고, i번 외계인은 d_i 만큼 떨어진 곳에서 a_i 시간에 나타난다. 이 외계인은 b_i 시간에 당신을 공격할 것이다. 따라서 정확히 b_i 시간 또는 그 이전에 처치해야 한다.

당신의 무기는 광자폭탄으로, 폭발력을 마음대로 조절할 수 있다. 만약 폭발력을 R로 설정하고 터뜨렸다면, 거리 R 이하의 모든 외계인이 즉사한다. 그리고 R 만큼의 연료를 소모한다.

공격당하지 않고 모든 외계인을 처치하는 데 필요한 최소 연료의 양을 구하여라.

입력 형식

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫 줄에 외계인의 수 n (1 ≤ n ≤ 300)이 주어지고, 다음 n 줄에 ai, bi, di (1 ≤ ai < bi ≤ 10 000; 1 ≤ di ≤ 10 000)가 주어진다.

출력 형식

각 테스트 케이스마다, 한 줄에 모든 외계인을 처치하는 데 필요한 최소 연료의 양을 출력한다.

예제 입력

1
3
1 4 4
4 7 5
3 4 7

예제 출력

7